COMMENT ⊗   VALID 00011 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	folio 725 galley 1
C00026 00003	folio 731 galley 2
C00046 00004	folio 735 galley 3
C00070 00005	folio 742 galley 4
C00096 00006	folio 748 galley 5
C00117 00007	folio 754 galley 6
C00139 00008	folio 758 galley 7
C00160 00009	folio 761 galley 8
C00174 00010	
C00175 00011	
C00176 ENDMK
C⊗;
folio 725 galley 1
    0  {U0}{H9L11M29}|π58320#Computer Programming!(Knuth/Addison-We
    1  sley)!f. 725!Ans!g. 1c|'{A6}|9|1|9|1|4|1|9|4|↔d|(.|4.|4.|4,|
    4  4|εa|β3,|5a|β2,|5a|β1,|5a|β0;|5a|βα_↓|β1,|5a|βα_↓|β2,|5.|4.|
    4  4.|'5.|4.|4.|4,|4b|β3,|4b|β2,|4b|β1,|4b|β0;|4b|βα_↓|β1,|4b|β
    5  α_↓|β2,|4.|4.|4.|)|↔f|4α=↓|4|↔d|(.|4.|4.|4,|4A|β3,|4A|β2,|4A
    5  |β1,|4A|β0:|4A|βα_↓|β1,|4A|βα_↓|β2,|4.|4.|4.|d5.|4.|4.|4,|4B
    5  |β3,|4B|β2,|4B|β1,|4B|β0:|4B|βα_↓|β1,|4B|βα_↓|β2,|4.|4.|4.|)
    5  |↔F|'{A4}|πif!!|εA|βj|4α=↓|4|↔d|(a|βk|mj|mα+↓|m1|βα_↓|β1,|4|
    6  1a|βk|mj|mα+↓|m1|βα_↓|β2,|4.|4.|4.|4,|5a|βk|mj|d5|ha|βk|mj|m
    6  α+↓|m1|βα_↓|β1,|5|nb|βk|mj|mα+↓|m1|βα_↓|β2,|4.|4.|4.|4,|4b|β
    6  k|mj|)|↔f,|4B|βj|4α=↓|4b|βk|mj|mα+↓|m1|βα_↓|β1|4.|4.|4.|4b|β
    6  k|mj,|;{A9}|πwhere |↔b|εk|βn|↔v |πis any in_nite 
   12  sequence of integers with |εk|βj|βα+↓|β1|4|¬Q|4k|βj.|'
   17  {A3}|π|≡1|≡1|≡.|9|4(The following algorithm works 
   21  both for addition or subtraction, depending on 
   28  whether the plus or minus sign is chosen.)|'!!|2Start 
   37  by setting |εk|4|¬L|4a|βn|βα+↓|β1|4|¬L|4a|βn|βα+↓|β2|4|¬L|4b
   39  |βn|βα+↓|β1|4|¬L|4b|βn|βα+↓|β2|4|¬L|40; |πthen 
   41  for |εm|4α=↓|40, 1, . . . , n|4α+↓|42 |πdo the 
   51  following : Set |εc|βm|4|¬L|4a|βm|4|¬N|4b|βm|4α+↓|4k; 
   55  |πthen if |εc|βm|4|¬R|42, |πset |εk|4|¬L|4|→α_↓1 
   60  |πand |εc|βm|4|¬L|4c|βm|4α_↓|42; |πif |εc|βm|4|¬W|40, 
   64  |πset |εk|4|¬L|41 |πand |εc|βm|4|¬L|4c|βm|4α+↓|42; 
   68  |πand if 0|4|¬E|4|εc|βm|4|¬E|41, |πset |εk|4|¬L|40.|'
   73  {A3}|π|≡1|≡2|≡.|9|4(a) Subtract (.|4.|4.|4|εa|β30a|β10) 
   76  |πfrom (.|4.|4.|4a|β40a|β20a|β0) |πin the negative 
   81  binary system. (b) Subtract (.|4.|4.|4|εb|β30b|β10) 
   86  |πfrom (.|4.|4.|4|εb|β40b|β20b|β0) |πin the binary 
   91  system.|'{A3}|≡1|≡3|≡.|9|4(1.90909090|4.|4.)|4α=↓|4(0.090909
   92  |4.|4.)|4α=↓|4|f1|d311|).|'{A3}|≡1|≡4|≡.|9|4!!!!|4|∂1|91|93|
   93  92|91!!|∂[5|4α_↓|44|εi]|'|L1|91|93|92|91|L[5|4α_↓|44i]>
   95  {B2}|L#####>|L1|91|93|92|91>| 1|9|L1|92|90|92>
   98  | 1|92|9|L1|92|93>| 1|91|93|9|L2|91>| 1|91|93|92|9|L1>
  101  {B2}|9|1|9|1|4|1|9|4###########|'| 0|91|90|93|9|L1|91|92|90|
  102  91|L[9|4α_↓|440i]>{A3}|π|≡1|≡5|≡.|9|4[|→α_↓|f10|d311|),|4|f1
  103  |d311|)], and the rectangle shown in Fig. A<6.|'
  111  {A4}|≡F|≡i|≡g|≡. |≡A|≡<|≡6|≡.|9|4Fundamental 
  113  region for quater-imaginary numbers.|'{A3}|≡1|≡6|≡.|9|4It 
  118  is tempting to try to do this in a very simple 
  129  way, by using the rule 2|4α=↓|4(1100)|ε|βi|βα_↓|β1 
  135  |πto take care of carries; but that leads to 
  144  a nonterminating method if we try to add one 
  153  to (11101)|ε|βi|βα_↓|β1|4α=↓|4|→α_↓1.|'!!|2|πThe 
  156  following solution does this by providing four 
  163  related algorithms (namely for adding or subtracting 
  170  1 or |εi). |πIf |ε|≤a |πis a string of zeros 
  180  and ones, let |ε|≤a|gP |πbe a string of zeros 
  189  and ones such that |ε(|≤a|gP)|βi|βα_↓|β1|4α=↓|4(|≤a|gP)|βi|β
  193  α_↓|β1|4α+↓|41; |πand let |ε|≤a|gα_↓|gP, |≤a|gQ, 
  198  |≤a|gα_↓|gQ |πbe de_ned similarly, with |→α_↓1, 
  204  |→α+↓|εi, |πand |ε|→α_↓i |πrespectively in place 
  210  of |→α+↓1. Then|'{A9}|ε|h(|≤ax0)|gα_↓|gP|4|∂α=↓|4|≤a|gα_↓|gQ
  213  x1; (|≤a1)|gα_↓|gP|4α=↓|4|≤a0.!!(|≤a0)|gα_↓|gQ|4|∂α=↓|4|≤a|g
  214  Q1; (|≤a1)|gα_↓|gQ|4α=↓|4|≤a|gα_↓|gP0.|E|n|;| (|≤a0)|gP|4|Lα
  216  =↓|4|≤a1; (|≤ax1)|gP|4α=↓|4|≤a|gQx0.| (|≤a0)|gQ|4|Lα=↓|4|≤a|
  217  gP1; (|≤a1)|gQ|4α=↓|4|≤a|gα_↓|gQ0.>| (|≤ax0)|gα_↓|gP|4|Lα=↓|
  219  4|≤a|gα_↓|gQx1; (|≤a1)|gα_↓|gP|4α=↓|4|≤a0.| (|≤a0)|gα_↓|gQ|4
  220  |Lα=↓|4|≤a|gQ1; (|≤a1)|gα_↓|gQ|4α=↓|4|≤a|gα_↓|gP0.>
  222  {A9}|πHere |εx |πstands for either 0 or 1, and 
  231  the strings are extended on the left with zeros 
  240  if necessary. The processes will clearly always 
  247  terminate. Hence every number of the form |εa|4α+↓|4bi 
  255  |πwith |εa, b |πintegers is representable in 
  262  the |εi|4α_↓|41 |πsystem.|'{A3}|≡1|≡7|≡.|9|4No; 
  266  the number |→α_↓1 cannot be so represented. (This 
  274  can be proved by constructing a set |εS |πas 
  283  in Fig. 1. We have the representations |ε|→α_↓i|4α=↓|4(0.111
  290  1111|4.|4.|4.)|β1|βα+↓|βi, i|4α=↓|4(100.1111111|4.|4.|4.)|g1
  291  |gα+↓|gi, |πbut |εS |πcontains no integer points 
  298  besides 0 and |ε|βα_↓i.) |πSee exercise 28, however.|'
  306  {A3}|≡1|≡8|≡.|9|4Let |εS|β0 |πbe the set of points 
  313  (|εa|β7a|β6a|β5a|β4a|β3a|β2a|β1a|β0)|βi|βα_↓|β1, 
  314  |πwhere each |εa|βk |πis 0 or 1. |ε(S|β0 |πis 
  323  given by the 256 interior dots shown in Fig. 
  332  1, if that picture is multiplied by 16.) We _rst 
  342  show that |εS |πis closed: If |εy|β1, y|β2, . 
  351  . . |πis an in_nite subset of |εS, |πwe have 
  361  |εy|βn|4α=↓|4|¬K|βk|β|¬R|β1|4a|βn|βk16|gα_↓|gk, 
  362  |πwhere each |εa|βn|βk |πis in |εS|β0. |πConstruct 
  369  a tree whose nodes are |ε(a|βn|β1,|4.|4.|4.|4,|4a|βn|βr), 
  375  |πfor |ε1|4|¬E|4r|4|¬E|4n, |πand let a node of 
  382  this tree be an ancestor of another node if it 
  392  is an initial subsequence of that node. By the 
  401  in_nity lemma this tree has an in_nite path |ε(a|β1, 
  410  a|β2, a|β3, . . .), |πand so |ε|¬K|βk|β|¬R|β1|4a|βk16|gα_↓|g
  417  k |πis a limit point of |ε|¬Ty|β1,|4y|β2,|4.|4.|4.|¬Y 
  424  |πin |εS.|'!!|2|πBy the answer to exercise 16, 
  432  all numbers of the form |ε(a|4α+↓|4bi)/16|gk 
  438  |πare representable, when |εa |πand |εb |πare 
  445  integers. Therefore if |εx |πand |εy |πare arbitrary 
  453  reals and |εk|4|¬R|41, |πthe number |εz|βk|4α=↓|4(|"l16|gkx|
  458  "L|4α+↓|4|"l16|gky|"Li)/16|gk |πis in |εS|4α+↓|4m|4α+↓|4ni 
  462  |πfor some integers |εm |πand |εn. |πIt can be 
  471  shown that |εS|4α+↓|4m|4α+↓|4ni |πis bounded 
  476  away from the origin when |ε(m,|4n)|4|=|↔6α=↓|4(0,|40). 
  482  |πConsequently if |ε|¬Gx|¬G |πand |ε|¬Gy|¬G |πare 
  488  su∃ciently small and |εk |πis su∃ciently large, 
  495  we have |εz|βk|4|¬A|4S, |πand lim|ε|βk|β|¬M|β|¬X|4z|βk|4α=↓|
  499  4x|4α+↓|4yi|4|¬A|4S.|'{A3}|π|≡1|≡9|≡.|9|4If |εm|4|¬Q|4u 
  502  |πor |εm|4|¬W|4l, |π_nd |εa|4|¬A|4D |πsuch that 
  508  |εm|4|"o|4a |π(modulo|4|εb); |πthe desired representation 
  513  will be a representation of |εm|¬S|4α=↓|4(m|4α_↓|4a)/b 
  519  |πfollowed by |εa. |πNote that |εm|4|¬Q|4u |πimplies 
  526  |εl|4|¬W|4m|¬S|4|¬W|4m; m|4|¬W|4l |πimplies |εm|4|¬W|4m|¬S|4
  529  |¬W|4u; |πso the algorithm terminates.|'!!|2[There 
  535  are no solutions when |εb|4α=↓|42. |πThe representation 
  542  will be unique i= 0|4|¬A|4|εD; |πnonunique representation 
  549  occurs for example when |εD|4α=↓|4|¬T|→α_↓3, 
  554  |→α_↓1, 7|¬Y, b|4α=↓|43, |πsince |ε(|≤a)|β3|4α=↓|4(|=∩377|=∩
  558  3|≤a)|β3. |πWhen |εb|4|¬E|43 |πit is not di∃cult 
  565  to show that there are exactly 2|ε|gb|gα_↓|g3 
  572  |πsolution sets |εD |πin which |¬G|εa|¬G|4|¬W|4b 
  578  |πfor all |εa|4|¬A|4D. |πFurthermore the set 
  584  |εD|4α=↓|4|¬T0, 1, 2|4α_↓|4|≤e|β2b|gn, 3|4α_↓|4|≤eb|gn,|4.|4
  587  .|4.|4, b|4α_↓|42|4α_↓|4|≤e|βb|βα_↓|β2b|gn, b|4α_↓|41|4α_↓|4
  589  b|gn|¬Y |πgives unique representations, for all 
  595  |εb|4|¬R|43 |πand |εn|4|¬R|41, |πwhen each |ε|≤e|βj 
  601  |πis 0 or 1.]|'{A3}|≡2|≡0|≡.|9|4(a) 0.|=∩1|=∩1|=∩1|4.|4.|4.|
  606  4α=↓|4|=∩1.888|4.|4.|4.|4α=↓|4|=∩18.|f1|d57|)|f1|d57|)|f1|d5
  606  7|)|4.|4.|4.|4α=↓|4|=∩18|f1|d57|).|f222|d5666|)|4|¬O|4|¬O|4|
  606  ¬O|4α=↓|4|¬O|4|¬O|4|¬O|4α=↓|4|=∩18|f123456|d5765432|).|f777|
  606  d51111|))*?|≡2|≡0|≡.|9|4(a) 0.|=∩1|=∩1|=∩1|4.|4.|4.|4α=↓|4|=∩
  607  1.888|4.|4.|4.|4α=↓|4|=∩18.|f1|d57|)|f1|d57|)|f1|d57|)|4.|4.
  607  |4.|4α=↓|4|=∩18|f1|d57|).|f222|d5666|)|4|¬O|4|¬O|4|¬O|4α=↓|4
  607  |¬O|4|¬O|4|¬O|4α=↓|4|=∩18|f123456|d5765432|).|f777|d5111|)|4
  607  .|4.|4. has nine representations. (b) A |ε``D-|πfraction'' 
  614  |ε.a|β1a|β2|4.|4.|4. |πalways lies between |→α_↓1/9 
  619  and |→α+↓71/9. Suppose |εx |πhas ten or more 
  627  |εD-|πdecimal representations. Then for su∃ciently 
  632  large |εk, 10|gkx |πhas ten representations which 
  639  di=er to the left of the decimal point: 10|ε|gkx|4α=↓|4n|β1|
  647  4α+↓|4f|β1|4α=↓|4|¬O|4|¬O|4|¬O|4α=↓|4n|β1|β0|4α+↓|4f|β1|β0 
  648  |πwhere |εf|βj |πis a |εD-|πfraction. By uniqueness 
  655  of integer representations, the |εn|βj |πare 
  661  distinct, say |εn|β1|4|¬W|4|¬O|4|¬O|4|¬O|4|¬W|4n|β1|β0, 
  664  |πhence |εn|β1|β0|4α_↓|4n|β1|4|¬R|49; |πbut this 
  668  implies |εf|β1|4α_↓|4f|β1|β0|4|¬R|49|4|¬Q|471/9|4α_↓|4(|→α_↓
  669  1/9), |πa contradiction. (c) Any number of the 
  677  form |ε0.a|β1a|β2|4.|4.|4.|4, |πwhere each |εa|βj 
  682  |πis |→α_↓1 or 8, equals |=∩1.|εa|ur|↔8|)1|)a|ur|↔8|)2|)|4.|
  687  4.|4.|4|πwhere |εa|ur|↔0|)j|)|4α=↓|4a|βj|4α+↓|49 
  689  |π(and it even has six |εmore |πrepresentations 
  696  |=∩18.|εa|ur|¬C|)1|)a|ur|¬C|)2|)|4.|4.|4. |πetc.).|'
  698  {A3}|≡2|≡1|≡.|9|4We can convert to such a representation 
  705  by using a method like that suggested in the 
  714  test for converting to balanced ternary.|'!!|2In 
  721  contrast to the systems of exercise 20, zero 
  729  can be represented in in_nitely many ways, all 
  737  obtained from |f1|d32|)|4α+↓|4|¬K|ε|βk|β|¬R|β1|4|→α_↓4|f1|d3
  739  2|)|4|¬O|410|gα_↓|gk |πor from the negative of 
  745  this representation, by multiplying it by a power 
  753  of ten. The representations of unity are 1|f1|d32|)|4α_↓|4|f
  760  1|d32|), |f1|d32|)|4α+↓|4|f1|d32|), 5|4α_↓|43|f1|d32|)|4α_↓|
  762  4|f1|d32|), 5|4α_↓|44|f1|d32|)|4α+↓|4|f1|d32|), 
  764  50|4α_↓|445|4α_↓|43|f1|d32|)|4α_↓|4|f1|d32|), 
  765  50|4α_↓|445|4α_↓|44|f1|d32|)|4α+↓|4|f1|d32|), 
  766  etc., where |→|¬N|f1|d32|)|4α=↓|4(|→|¬N4|f1|d32|))(10|gα_↓|g
  768  1|4α+↓|410|gα_↓|g2|4α+↓|4.|4.|4.). [|εAMM |≡5|≡7 
  771  (1950), 90<93.]|'{A3}|π|≡2|≡2|≡.|9|4Assuming 
  774  that we have some approximation |εb|βn|4.|4.|4.|4b|β1b|β0 
  780  |ππ*?|π|≡2|≡2|≡.|9|4Assuming that we have some 
  785  approximation |εb|βn|4.|4.|4.|4b|β1b|β0 |πwith 
  788  error |¬K|ε|β0|β|¬E|βk|β|¬E|βn|4b|βk10|gk|4α_↓|4x|4|¬Q|410|g
  789  α_↓|gt |πfor |εt|4|¬Q|40, |πwe will show how 
  796  to reduce the error by approximately 10|ε|gα_↓|gt. 
  803  |π(The process can be started by _nding a suitable 
  812  |¬K|ε|β0|β|¬E|βk|β|¬E|βn|4b|βk10|gk|4|¬Q|4x; 
  813  |πthen a _nite number of reductions of this type 
  822  will make the error less than |ε|≤e.) |πSimply 
  830  choose |εm|4|¬Q|4n |πso large that the decimal 
  837  representation of |ε|→α_↓10|gm|≤a |πhas a one 
  843  in position |ε10|gα_↓|gt |πand no ones in positions 
  851  10|ε|gα_↓|gt|gα+↓|g1, 10|gα_↓|gt|gα+↓|g2,|4.|4.|4.|4,|410|gn
  852  . |πThen |ε10|gm|≤a|4α+↓|4|π(a suitable sum of 
  858  powers of 10 between |ε10|gm |πand |ε10|gn)|4α+↓|4|¬K|β0|β|¬
  864  E|βk|β|¬E|βn|4b|βk10|gk|4|¬V|4|¬K|β0|β|¬E|βk|β|¬E|βn|4b|βk10
  864  |gk|4α_↓|410|gα_↓|gt.|'{A3}|π|≡2|≡3|≡.|9|4The 
  866  set |εS|4α=↓|4|¬T|¬K|βk|β|¬R|β1|4a|βkb|gα_↓|gk|4|¬G|4a|βk|4|
  867  ¬A|4D|¬T |πis closed as in exercise 18, hence 
  875  measurable, and in fact it has positive measure. 
  883  Since |εbS|4α=↓|4|↔w|βa|β|¬A|βD|4(a|4α+↓|4S), 
  885  |πwe have |εb|≤m(S)|4α=↓|4|≤m(bS)|4|¬E|4|¬K|βa|β|¬A|βD|4|≤m(
  887  a|4α+↓|4S)|4α=↓|4|¬K|βa|β|¬A|βd|4|≤m(S)|4α=↓|4b|≤m(S), 
  888  |πand we must have |ε|≤m{H11}({H9}(a|4α+↓|4S)|4|↔Q|4(a|¬S|4α
  892  +↓|4S){H11}){H9}|4α=↓|40 |πwhen |εa|4|=|↔6α=↓|4a|¬S|4|¬A|4D.
  894   |πNow |εT |πis a union of countably many sets 
  904  of the form |ε10|gk{H11}({H9}n|4α+↓|4((a|4α+↓|4S)|4|↔Q|4(a|¬
  907  S|4α+↓|4S)){H11}){H9}, a|4|=|↔6α=↓|4a|¬S, |πeach 
  910  of measure zero.|'!!|2[The set |εT |πcannot be 
  918  empty, since the real numbers cannot be written 
  926  as a countable union of disjoint, closed, bounded 
  934  sets. If |εD |πhas less than |εb |πelements, 
  942  the set of numbers representable with radix |εb 
  950  |πand digits from |εD |πhas measure zero. If 
  958  |εD |πhas more than |εb |πelem5, 0|4|¬E|4a|¬S|4|¬W|42|¬Y, 
  965  |πfor |εk|4|¬R|40. |π[R. W. Graham and D. W. 
  973  Matula have shown that there are no more sets 
  982  of integer digits with these properties. And 
  989  Andrew Odlyzko has shown that the restriction 
  996  to integers is super⊗ous, in the sense that if 
 1005  the smallest two elements of |εD |πare 0 and 
 1014  1, all the digits must be integers. Proof: Let 
 1023  |εA|4α=↓|4|¬T(d|βk|4.|4.|4.|4d|β0)|βb|4|¬G|4d|βj|4|¬A|4D|¬Y,
 1023   |πthen [0,|4|¬X)|4α=↓|4|↔w|ε|βa|β|¬A|βA|4(a|4α+↓|4S) 
 1026  |πand |ε(a|4α+↓|4S)|4|↔Q|4(a|¬S|4α+↓|4S) |πhas 
 1029  measure zero for |εa|4|=|↔6α=↓|4a|¬S|4|¬A|4A. 
 1033  |πWe have (0,|41)|4|↔Y|4|εS, |πand by induction 
 1039  on |εm |πwe will prove that |ε(m,|4m|4α+↓|41)|4|↔Y|4a|βm|4α+
 1045  ↓|4S |πfor some |εa|βm. |πLet |εa|βm |πbe maximal 
 1053  in |εS |πwith |ε(m,|4m|4α+↓|4|≤e)|↔Q|4(a|βm|4α+↓|4S) 
 1057  |πof positive measure for all |ε|≤e|4|¬Q|40. 
 1063  |πThen |εa|βm|4|¬E|4m, |πand |εa|βm |πmust be 
 1069  an integer lest |εa|β|"l|βa|mm|β|"L|4α+↓|4S |πoverlap 
 1074  |εa|βm|4α+↓|4S |πtoo much. If |εa|βm|4|¬Q|40, 
 1079  |πthe fact that |εm|4α_↓|4a|βm, m|4α_↓|4a|βm|4α+↓|41)|4|↔Q|4
 1083  S |πis of positive measure implies by induction 
 1091  that this measure is 1, and |ε(m,|4m|4α+↓|41)|4|↔Y|4a|βm|4α+
 1097  ↓|4S |πsince |εS |πis closed. If |εa|βm|4α=↓|40 
 1104  |πand |ε(m,|4m|4α+↓|41)|4|=|↔6|↔Y|4S, |πthe maximality 
 1108  of |εq|βm |πshows that |εm|4|¬W|4a|ur|↔0|)m|)|4|¬W|4m|4α+↓|4
 1112  1 |πfor some |εa|ur|↔0|)m|)|4|¬A|4A, |πwhere 
 1117  |ε(m,|4a|ur|↔0|)m|))|4|↔Y|4S; |πbut then 1|4α+↓|4|εS 
 1121  |πoverlaps |εa|ur|↔0|)m|)|4α+↓|4S.]|'|π!!|2If 
 1124  we drop the restriction 0|4|¬A|4|εD |πthere |εare 
 1131  |πmany other cases, some of which are quite interesting, 
 1140  especially the sets |¬T1, 2, 3, 4, 5, 6, 7, 8, 
 1151  9, 10|¬Y, |¬T1, 2, 3, 4, 5, 51, 52, 53, 54, 55|¬Y, 
 1163  and |¬T2, 3, 4, 5, 6, 52, 53, 54, 55, 56|¬Y. 
 1174  Alternatively if we allow negative digits we 
 1181  obtain many other solutions by the method of 
 1189  exercise 19, plus further sets like |¬T|→α_↓1, 
 1196  0, 1, 2, 3, 4, 5, 6, 7, 18|¬Y which don't meet 
 1208  the conditions of that exercise; it appears hopeless 
 1216  to _nd a nice characterization of all solutions 
 1224  with negative digits.]|'{A3}|≡2|≡5|≡.|9|4A positive 
 1229  number whose base |εb |πrepresentation has |εm 
 1236  |πconsectuve |ε(b|4α_↓|41)'|πs to the right of 
 1242  the decimal point must have the form |εc/b|gn|4α+↓|4(b|gm|4α
 1249  _↓|4|≤u)/b|gn|gα+↓|gm, |πwhere 0|4|¬W|4|≤u|4|¬E|41 
 1252  and |εc, n |πare nonnegative integers. So if 
 1260  |εu/v |πhas this form, we _nd that |εb|gm|gα+↓|gnu|4α=↓|4b|g
 1267  mcv|4α+↓|4b|gmv|4α_↓|4|≤uv. |πTherefore |ε|≤uv 
 1270  |πis an integer which is a multiple of |εb|gm. 
 1279  |πBut |ε0|4|¬W|4|≤uv|4|¬E|4v|4|¬W|4b|gm. |π(There 
 1282  can be arbitrarily long runs of other digits 
 1290  |εdddddddd, |πif |ε0|4|¬E|4d|4|¬W|4b|4α_↓|41, 
 1293  |πfor example in the representation of |εd/(b|4α_↓|41).{H11}
 1299  ){H9}|'|H*?{U0}{H9L11M29}|π58320#Computer Programming!(Knuth/
folio 731 galley 2
 1301  Addison-Wesley)!f. 731!Ans!g. 2c|'{A6}|≡2|≡6|≡.|9|4The 
 1305  proof of ``su∃ciency'' is  straightforward generalization 
 1312  of the usual proof for base |εb, |πby successively 
 1321  constructing the desired representation. The 
 1326  proof of ``necessity'' breaks into two parts: 
 1333  If |ε|≤b|βn|βα↓|β1 |πis greater than |ε|¬K|βk|β|¬E|βn|4c|βk|
 1338  ≤b|βk |πfor some |εn, |πthen |ε|≤b|βn|βα+↓|β1|4α_↓|4|≤e 
 1344  |πhas no representation for small |ε|≤e. |πIf 
 1351  |ε|≤b|βn|βα↓|β1|4|¬E|4|¬K|βk|β|¬E|βn|4c|βk|≤b|βk 
 1352  |πfor all |εn, |πbut equality does not always 
 1360  hold, we can show there are two representations 
 1368  for certain |εx. |π[See |εTransactions of the 
 1375  Royal Society of Canada, |πseries III, |≡4|≡6 
 1382  (1952), 45<55.]|'{A3}|≡2|≡7|≡.|9|4Proof by induction 
 1387  on |ε|¬Gn|¬G: |πIf |εn |πis even we must take 
 1396  |εe|β0|4|¬Q|40, |πand tahe result then follows 
 1402  by induction, since |εn/2 |πhas a unique such 
 1410  representation. If |εn |πis odd, we must take 
 1418  |εe|β0|4α=↓|40, |πand the problem reduces to 
 1424  representing |ε|→α_↓(n|4α_↓|41)/2; |πthe latter 
 1428  quantity is either zero or one, when there is 
 1437  obviously only one way to proceed, or it has 
 1446  a unique reversing representation by induction.|'
 1452  {A3}|≡2|≡8|≡.|9|4A proof like that of exercise 
 1458  27 may be given. Note that |εa|4α↓|4bi |πis a 
 1467  multiple of |ε1|4α+↓|4i |πby a complex integer 
 1474  if and only if |εa|4α+↓|4b |πis even.|'{A3}|≡2|≡9|≡.|9|4It 
 1482  su∃ces kto prove that any collection |εT|β0, 
 1489  T|β1, T|β2, . . . |πsatisfying Property B may 
 1498  be obtained by collapsing some sollcetion |εS|β0, 
 1505  S|β1, S|β2, . . . , |πwhere |εS|β0|4α=↓|4|¬T0,|41,|4.|4.|4.|
 1512  4,|4b|4α_↓|41|¬Y |πand all elemenats of |εS|β1, 
 1518  S|β2, . . . |πare multiples of |εb.|'|π!!|2To 
 1527  prove the latter statement, we may assume that 
 1535  1|4|¬A|4|εT|β0 |πand that theare is a least element 
 1543  |εb|4|¬Q|41 |πsuch that |εb|4|=|↔6|¬A|4T|β0. 
 1547  |πWe will prove, by induction on |εn, |πthat 
 1555  if |εnb|4|=|↔6|¬A|4T|β0, |πthen |εnb|4α↓|41, 
 1559  bn|4α↓|42, . . . , nb|4α↓|4b|4α_↓|41 |πare not 
 1567  in any of the |εT|βj|π's; but if |εnb|4|¬A|4T|β0, 
 1575  |πthen so are |εnb|4α+↓|41, . . . , nb|4α+↓|4b|4α_↓|41. 
 1584  |πThe result then follows with |εS|β1|4α=↓|4|¬Tnb|4|¬G|4nb|4
 1589  |¬A|4T|β0|¬Y, S|β2|4α=↓|4T|β1, S|β3|4α=↓|4T|β2, 
 1592  |πetc.|'!!|2If |εnb|4|=|↔6|¬A|4T|β0, |πthen |εnb|4α=↓|4t|β0|
 1596  4α+↓|4t|β1|4|¬O|4|¬O|4|¬O|4, |πwhere |εt|β1, 
 1599  t|β2, . . . |πare multiples of |εb; |πhence |εt|β0|4|¬W|4nb 
 1609  |πis a multiple of |εb. |πBy induction, |ε(t|β0|4α+↓|4k)|4α+
 1616  ↓|4t|β1|4α+↓|4t|β2|4α+↓|4|¬O|4|¬O|4|¬O |πis the 
 1619  representation of |εnb|4α+↓|4k, |πfor 0|4|¬W|4|εk|4|¬W|4b; 
 1624  |πhence |εnb|4α+↓|4k|4|=|↔6|¬A|4T|βj |πfor any 
 1628  |εj.|'|π!!|2If |εnb|4|¬A|4T|β0 |πand 0|4|¬W|4|εk|4|¬W|4b, 
 1633  |πlet the representation of |εnb|4α+↓|4k |πbe 
 1639  |εt|β0|4α+↓|4t|β1|4α+↓|4|¬O|4|¬O|4|¬O|4. |πWe 
 1641  cannot have |εt|βj|4α=↓|4nb|4α+↓|4k |πfor |εj|4|¬R|41, 
 1646  |πlest |εnb|4α+↓|4b |πhave two representations 
 1651  |ε(b|4α_↓|4k)|4α+↓|4|¬O|4|¬O|4|¬O|4α+↓|4(nb|4α+↓|4k)|4α+↓|4|
 1651  ¬O|4|¬O|4|¬O|4α=↓|4(nb)|4α+↓|4|¬O|4|¬O|4|¬O|4α+↓|4b|4α+↓|4|¬
 1651  O|4|¬O|4|¬O|4. |πBy induction, |εt|β0|4|πmod|4|εb|4α=↓|4k; 
 1655  |πand the representation |εnb|4α=↓|4(t|β0|4α_↓|4k)|4α↓|4t|β1
 1658  |4α↓|4|¬O|4|¬O|4|¬O |πimplies that |εt|β0|4α=↓|4nb|4α+↓|4k.|
 1661  '|π!!|2[Reference: |εNieuw Archief voor Wiskunde 
 1667  (3) |≡4 (1956), 15<17. |πA _nite analog of this 
 1676  result was derived by P. A. MacMahon, |εCombinatory 
 1684  Analysis |≡1 (1915), 217<223.]|'{A3}|π|≡3|≡0|≡.|9|4a) 
 1689  Let |εA|βj |πbe the set of numbers |εn |πwhose 
 1698  representation does not involve |εb|βj; |πthen 
 1704  by the uniqueness property, |εn|4|¬A|4A|βj |πi= 
 1710  |εn|4α+↓|4b|βj|4|=|↔6|¬A|4A|βj. |πConsequently 
 1712  |βn|4|¬A|4A|βj i= |εn|4α+↓|42b|βj|4|¬A|4A|βj. 
 1715  |πIt follows that, for |εj|4|=|↔6α=↓|4k, n|4|¬A|4A|βj|4|↔Q|4
 1720  A|βk |πi= |εn|4α+↓|42b|βjb|βk|4|¬A|4A|βj|4|↔Q|4A|βk. 
 1723  |πLet |εm |πbe the number of integers |εn|4|¬A|4A|βj|4|↔Q|4A
 1730  |βk |πsuch that 0|4|¬E|4|εn|4|¬W|42b|βjb|βk. 
 1734  |πThen there are exactly |εm |πintegers in the 
 1742  same range which are in |εA|βj |πbut not |εA|βk, 
 1751  |πexactly |εm |πin |εA|βk |πbut not |εA|βj, |πand 
 1759  exactly |εm |πin neither |εA|βj |πnor |εA|βk; 
 1766  |πhence |ε4m|4α=↓|42b|βjb|βk. |πTherefore |εb|βj 
 1770  |πand |εb|βk |πckan*?*?d this interval. In this 
 1777  range 3|4|¬M|4|→α_↓1|4|¬M|4|→α_↓2|4|¬M|46|4|¬M|48|4|¬M|42|4|
 1778  ¬M|42|4|¬M|47|4|¬M|40 and 4|4|¬M|41|4|¬M|45|4|¬M|46. 
 1781  Thus 1|4α=↓|4|≥ |¬O 2|g0 α_↓ 13 |¬O 2|g1 α+↓ 
 1790  7 |¬O 2|g2 α_↓ 13 |¬O 2|g3 α_↓ 13 |¬O 2|g5 α_↓ 
 1802  13 |¬O 2|g9 α+↓ 7 |¬O 2|g1|g0.|'!!|2|εNote|*/:|\ 
 1810  |πThe choice |εd|β0, d|β1, d|β2,|4.|4.|4.|4α=↓|45, 
 1815  |→α_↓3, 3, 5, |→α_↓3, 3, . . . |πalso yields 
 1825  a binary basis. For further details see |εMath. 
 1833  Comp. |≡1|≡8 (1964), 537<546; |πA. D. Sands, 
 1840  |εActa Mathematica, |πAcad. Sci. Hung., |≡8 (1957), 
 1847  65<86.|'{A3}|≡3|≡1|≡.|9|4(See also the related 
 1852  exercises 3.2.2<11, 4.3.2<13, 4.6.2<22.)|'!!|2a)|9By 
 1857  multiplying numerator andffd*?*?*?!!|2a)|9By multiplying 
 1861  numerator and denominator by suitable powers 
 1867  of 2, we may assume that |εu|4α=↓|4(.|4.|4.|4u|β2u|β1u|β0)|β
 1873  2 |πand |εv|4α=↓|4(.|4.|4.|4v|β2v|β1v|β0)|β2, 
 1876  |πwhere |εv|β0|4α=↓|41. |πThe following computational 
 1881  method now determines |εw, |πusing the notation 
 1888  |εu|g(|gn|g) |πto stand for the integer |ε(u|βn|βα_↓|β1|4.|4
 1894  .|4.|4u|β0)|β2|4α=↓|4u|4|πmod|4|ε2|gn |πwhen 
 1896  |εn|4|¬Q|40:|'|π!!|2Let |εw|β0|4α=↓|4u|β0. |πFor 
 1900  |εn|4α=↓|41, 2, . . . , |πassume that we have 
 1910  found an integer |εw|g(|gn|g)|4α=↓|4|ε(w|βn|βα_↓|β1|4.|4.|4.
 1913  |4w|β0)|β2 |πsuch that |εu|g(|gn|g)|4|"o|4v|g(|gn|g)w|g(|gn|
 1916  g) |π(modulo 2|ε|gn). |πThen |εu|g(|gn|gα+↓|g1|g)*444*?*?|4α=↓|
 1920  4u|β0. |πFor |εn|4α=↓|41, 2, . . . , |πassume 
 1929  that we have found an integer |εw|g(|gn|g)|4α=↓|4|ε(w|βn|βα_
 1935  ↓|β1|4.|4.|4.|4w|β0)|β2 |πsuch that |εu|g(|gn|g)|4|"o|4v|g(|
 1938  gn|g)w|g(|gn|g) |π(modulo 2|ε|gn). |πThen |εu|g(|gn|gα+↓|g1|
 1942  g)|4|"o|4v|g(|gn|gα+↓|g1|g)w|g(|gn|g) |π(modulo 
 1944  2|ε|gn), |πhence we may let |εw|βn|4α=↓|40 |πor 
 1951  1 according as |ε(u|g(|gn|gα+↓|g1|g)|4α_↓|4v|g(|gn|gα+↓|g1|g
 1954  )w|g(|gn|g)|π)mod|42|ε|gn|gα+↓|g1 |πis 0 or |ε2|gn.|'
 1959  !!|2|πb)|9Find the smallest integer |εk |πsuch 
 1965  that |ε2|gk|4|"o|41 |π(modulo |ε2n|4α+↓|41). 
 1969  |πThen |ε1/(2n|4α+↓|41)|4α=↓|4m/(2|gk|4α_↓|41) 
 1971  |πfor some integer |εm, 1|4|¬E|4m|4|¬W|42|gk|gα_↓|g1. 
 1976  |πLet |ε|≤a |πbe the |εk-|πbit binary representation 
 1983  of |εm; |πthen |ε(0.|≤a|≤a|≤a|4.|4.|4.)|β2 |πtimes 
 1988  |ε2n|4α+↓|41 |πis (0.111|4.|4.|4.)|β2|4α=↓|41 
 1991  |πin the binary system, and (.|4.|4.|4|ε|≤a|≤a|≤a)|β2 
 1997  |πtimes |ε2n|4α+↓|41 |πis (.|4.|4.|4111)|β2|4α=↓|4|→α_↓1 
 2001  in the 2-adic system.|'!!|2c)|9If |εu |πis rational, 
 2009  say |εu|4α=↓|4m/2|gtn |πwhere |εn |πis odd and 
 2016  positive, the 2-adic representation of |εu |πis 
 2023  periodic, because the set of numbers with periodic 
 2031  expansions includes |→α_↓1/|εn |πand is closed 
 2037  under the operations of negation, division by 
 2044  2, and addition.|'!!|2d)|9The square of any number 
 2052  of the form (.|4.|4.|4|εu|β2u|β11)|β2 |πhas the 
 2058  form (.|4.|4.|4001)|β2, hence the condition is 
 2064  necessary. To show the su∃ciency, use the following 
 2072  procedure to compute |εv|4α=↓|4{H10}|¬H{H9}|v4n|) 
 2076  |πwhen |εn |πmod|48|4α=↓|41:|'{A3}{I3.2H}!!|2|≡H|≡1|≡.|9Set 
 2080  |εn|4|¬L|4(n|4α_↓|41)/8, k|4|¬L|42, v|β0|4|¬L|41, 
 2083  v|β1|4|¬L|40, v|4|¬L|41.|'{A3}|π!!|2|≡H|≡2|≡.|9If 
 2086  |εn |πis even, set |εv|βk|4|¬L|40, n|4|¬L|4n/2. 
 2092  |πOtherwise set |εv|βk|4|¬L|41, n|4|¬L|4(n|4α_↓|4v|4α_↓|42|g
 2095  k|gα_↓|g1)/2, v|4|¬L|4v|4α+↓|42|gk.|'!!|2|π|≡H|≡3|≡.|9Increa
 2097  se |εk |πby 1 and return to H2.|'{A3}{IC}|≡3|≡2|≡.|9|4A 
 2106  generalization appears in |εMath. Comp. |≡2|≡9 
 2112  (1975), 84<86.|'{A25}{H10L12}|π|∨S|∨E|∨C|∨T|∨I|∨O|∨N|9|∨4|∨.
 2114  |∨2|∨.|∨1|'{A11}{H9L11}|9|1|≡1|≡.|9|4|εN|4α=↓|4(62, 
 2116  |→α+↓.60|422|452|400); h|4α=↓|4(37,|4|→α+↓.10|454|450|400). 
 2118  |πNote that 10|εh |πwould be (38,|4|→α+↓.01|405|445|400).|'
 2124  {A3}|9|1|≡2|≡.|9|4|εb|gE|gα_↓|gq(1|4α_↓|4b|gα_↓|gp), 
 2125  b|gα_↓|gq|gα_↓|gp; b|gE|gα_↓|gq(1|4α_↓|4b|gα_↓|gp), 
 2127  b|gα_↓|gq|gα_↓|g1.|'{A3}|π|9|1|≡3|≡.|9|4When 
 2129  |εe |πdoes not have its smallest value, the most 
 2138  signi_cant ``one'' bit (which appears in all 
 2145  such normalized numbers) need not appear in the 
 2153  computer word. [This idea appeared in Zuse's 
 2160  machine in 1936.]|'|9|1|≡4|≡.|9|4(51, |→α+↓.10209877); 
 2165  (50,|4|→α+↓.12346000); (53,|4|→α+↓.99999999). 
 2167  The third answer would be (54,|4|→α+↓.10000000) 
 2173  if the _rst operand had been (45,|4|→α_↓.50000000).|'
 2180  {A3}|9|1|≡5|≡.|9|4If |εx|4|¬Z|4y |πand |εm |πis 
 2185  an integer then |εmb|4α+↓|4x|4|¬Z|4mb|4α+↓|4y. 
 2189  |πAnother crucial property is that |εx/b |πand 
 2196  |εy/b |πwill round to the same integer, whenever 
 2204  |εx|4|¬Z|4y.|'!!|2|πNow if |εb|gα_↓|gp|gα_↓|g2F|βv|4|=|↔6α=↓
 2207  |4f|βv |πwe must have |ε(b|gp|gα+↓|g2fv)|πmod|4|εb|4|=|↔6α=↓
 2211  |40; |πhence the transformation leaves |εf|βv 
 2217  |πunchanged unless |εe|βu|4α_↓|4e|βv|4|¬R|42. 
 2220  |πSince |εu |πwas normalized, it is nonzero and 
 2228  |ε|¬Gf|βu|4α+↓|4f|βv|¬G|4|¬Q|4b|gα_↓|g1|4α_↓|4b|gα_↓|g2|4|¬R
 2228  |4b|gα_↓|g2: |πthe leading nonzero digit of |εf|βu|4α+↓|4f|β
 2234  v |πmust be at most two places to the right of 
 2245  the radix point, and the rounding operation will 
 2253  convert |εb|gp|gα+↓|gj(f|βu|4α+↓|4f|βv) |πto 
 2256  an integer, where |εj|4|¬E|41. |πThe proof will 
 2263  be complete if we can show that |εb|gp|gα+↓|gj|gα+↓|g1()f|βu
 2270  |4α+↓|4f|βv)|4|¬Z|4b|gp|gα+↓|gj|gα+↓|g1(f|βu|4α+↓|4b|gα_↓|gp
 2270  |gα_↓|g2F|βv). |πBy the previous paragraph, we 
 2276  have |εb|gp|gα+↓|g2(f|βu|4α+↓|4f|βv)|4|¬Z|4b|gp|gα+↓|g2f|βu|
 2277  4α+↓|4F|βv|4α=↓|4b|gp|gα+↓|g2(f|βu|4α+↓|4b|gα_↓|gp|gα_↓|g2F|
 2277  βv), |πwhich implies the desired result for all 
 2285  |εj|4|¬E|41.|'!!|2|πNote that, when |εb|4|¬Q|42 
 2290  |πis even, such an integer |εF|βv |πalways exists; 
 2298  but when |εb|4α=↓|42 |πwe require |εp|4α+↓|43 
 2304  |πbits (let |ε2F|βv |πbe an integer). When |εb 
 2312  |πis odd, an integer |εF|βv |πalways exists except 
 2320  in the case of division, when a remainder of 
 2329  |ε|f1|d32|)b |πis possible.|'{A3}|9|1|≡6|≡.|9|4(Consider 
 2333  the case |εe|βu|4α=↓|4e|βv, f|βu|4α=↓|4|→α_↓f|βv 
 2337  |πin Program A.) Register A retains its previous 
 2345  sign, as in |¬a|¬d|¬d.|'{A3}|9|1|≡7|≡.|9|4Say 
 2350  that a number is normalized i= it is zero or 
 2360  its fraction part satis_es |f1|d36|)|4|¬W|4|¬G|εf|¬G|4|¬W|4|
 2364  f1|d32|). |πA |ε(p|4α+↓|41)-|πplace accumulator 
 2368  su∃ces for addition and subtraction; rounding 
 2374  (except during division) is equivalent to truncation. 
 2381  A very pleasant system indeed*3 We might represent 
 2389  numbers with excess-zero exponent, inserted between 
 2395  the _rst and subsequent digits of the fraction, 
 2403  and complemented if the fraction is negative, 
 2410  so that _xed-point order is preserved.|'{A3}|9|1|≡8|≡.|9|4(a
 2416  ) (06, |→α+↓.12345679)|4|↔V|4(06,|4|→α_↓.12345678), 
 2419  (01,|4|→α+↓.10345678)|4|↔V|4(00, |→α_↓.94000000); 
 2421  (b) (99, |→α+↓.87654321)|4|↔V|4itself, (99, |→α+↓.99999999)|
 2425  4|↔V|4(91, |→α+↓.50000000).|'{A3}|9|1|≡9|≡.|9|4|εa|4α=↓|4(|→
 2427  α_↓50, |→α+↓.10000000), b|4α=↓|4(|→α_↓41, |→α+↓.20000000), 
 2431  c|4α=↓|4a, d|4α=↓|4(|→α_↓41, |→α+↓.80000000), 
 2434  y|4α=↓|4(11, |→α+↓.10000000).|'{A3}|π|≡1|≡0|≡.|9|4(50,|4|→α+
 2436  ↓.99999000)|4|↔V|4(55,|4|→α+↓.99999000).|'|Hβ*?*?*?*?{U0}{H9L11M
folio 735 galley 3
 2437  29}|π58320#Computer Programming!(Knuth/Addison-Wesley)!f. 
 2439  735!Ans!g. 3c|'{A6}|≡1|≡1|≡.|9|4(50,|4|→α+↓.10000001)|4|↔V|4
 2441  (50,|4|→α+↓.99999990).|'{A3}|≡1|≡2|≡.|9|4If 0|4|¬W|4|ε|¬Gf|β
 2443  u|¬G|4|¬W|4|¬Gf|βv|¬G, |πthen |ε|¬Gf|βu|¬G|4|¬E|4|¬Gf|βv|¬G|
 2445  4α_↓|4b|gα_↓|gp; |πhence |ε1/b|4|¬W|4|¬Gf|βu/f|βv|¬G|4|¬E|41
 2447  |4α_↓|4b|gα_↓|gp/|¬Gf|βv|¬G|4|¬W|41|4α_↓|4b|gα_↓|gp. 
 2448  |πIf 0|4|¬W|4|¬Gf|βv|¬G|4|¬E|4|¬Gf|βu|¬G, |πwe 
 2451  have |ε1/b|4|¬W|4|¬Gf|βu/f|βv|¬G/b|4|¬E|4(1|4α_↓|4b|gα_↓|gp)
 2452  /(1/b)/b|4α=↓|41|4α_↓|4b|gα_↓|gp.|'{A3}|π|≡1|≡3|≡.|9|4See 
 2454  J. Michael Yohe, |εIEEE Transactions |π|≡C|≡-|≡2|≡2 
 2460  (1973), 577<586.|'{A3}|≡1|≡4|≡.|9|4|∂|¬f|¬i|¬x!|∂|¬s|¬t|¬j|9
 2462  |3!|∂|¬9|¬f!!!!|9|3|∂Float-to-_x subroutine:|'
 2464  |L|L|¬s|¬t|¬a|L|¬t|¬e|¬m|¬p>|L|L|¬l|¬d|¬1|L|¬t|¬e|¬m|¬p|≤#|¬
 2465  e|¬x|¬p|≤&|LrI1|4|¬L|4|εe.>|π|L|L|¬s|¬l|¬a|L|¬1|LrA|4|¬L|4|→
 2466  |¬N|εf|1f|1f|1f|10.>|L|L|¬j|¬a|¬z|L|¬9|¬f|L|πIs 
 2468  input zero?>|L|L|¬d|¬e|¬c|¬1|L|¬1>|L|L|¬c|¬m|¬p|¬a|L|≤$|¬0|≤
 2471  $|≤#|¬1|¬.|¬1|≤&|LIf leading byte is zero,>|L|L|¬j|¬e|Lα/↓|≤
 2476  */|¬4|L!shift left again.>|L|L|¬e|¬n|¬n|¬1|L|≤*/|¬q|≤*/|¬4|¬,|¬
 2479  1>|L|L|¬j|¬1|¬n|L|¬f|¬i|¬x|¬o|¬v|¬f|¬l|¬o|LIs 
 2481  magnitude too large?>|L|L|¬e|¬n|¬t|¬x|L|¬0>|L|L|¬s|¬r|¬a|¬x|
 2485  L|¬0|¬,|¬1>|L|L|¬c|¬m|¬p|¬x|L|≤$|¬1/|2/|¬2|≤$>
 2487  |L|L|¬j|¬l|L|¬9|¬f>|L|L|¬j|¬g|Lα/↓|≤%|¬2>|L|L|¬j|¬a|¬o|L|¬9|
 2489  ¬f>|L|L|¬s|¬t|¬a|Lα/↓|≤%|¬1|≤#|¬0|¬;|¬0|≤&|LRound, 
 2491  if necessary.>|L|L|¬i|¬n|¬c|¬a|L|¬1|LAdd |→|¬N1 
 2495  (over⊗ow is impossible).>|L|¬9|¬h|L|¬j|¬m|¬p|Lα/↓|LExit 
 2499  from subroutine.>{A3}|≡1|≡5|≡.|9|4|∂|¬F|¬P|9|3|∂|¬s|¬t|¬j|9|
 2501  3|∂|¬e|¬x|¬i|¬t|¬f!!!!!!|∂Fractional part subroutine:|'
 2504  |L|L|¬j|¬o|¬v|L|¬o|¬f|¬l|¬o|LEnsure over⊗ow is 
 2507  o=.>|L|L|¬s|¬t|¬a|L|¬t|¬e|¬m|¬p|L|¬t|¬e|¬m|¬¬*?*?*?¬s|¬t|¬a|L|¬
 2508  t|¬e|¬m|¬p|L|¬t|¬e|¬m|¬p|4|¬L|4|εu.>|L|L|π|¬e|¬n|¬t|¬x|L|¬0>
 2510  |L|L|¬s|¬l|¬a|L|¬1|LrA|4|¬L|4|εf|βu.>|L|L|¬l|¬d|¬s|L|¬t|¬e|¬
 2511  m|¬p|≤#|¬e|¬x|¬p|≤&|L|πrI2|4|¬L|4|εe|βu.>|L|L|π|¬d|¬e|¬c|¬2|
 2512  L|¬q>|L|L|¬j|¬2|¬n|¬p|Lα/↓|≤%|¬3>|L|L|¬s|¬l|¬a|L|¬0|¬,|¬2|LR
 2514  emove integer part of |εu.>|L|L|π|¬e|¬n|¬t|¬2|L|¬0>
 2520  |L|L|¬j|¬a|¬n|¬n|L|¬1|¬f>|L|L|¬e|¬n|¬n|¬2|L|¬0|¬,|¬2|LFracti
 2521  on is negative: _nd>|L|L|¬s|¬r|¬a|¬x|L|¬0|¬,|¬2|L!its 
 2526  complement.>|L|L|¬e|¬n|¬t|¬2|L|¬0>|L|L|¬j|¬a|¬z|Lα/↓|≤%|¬2>
 2529  |L|L|¬i|¬n|¬c|¬a|L|¬1>|L|L|¬a|¬d|¬d|L|¬w|¬m|¬1|LAdd 
 2531  word size minus one.>|L|¬1|¬h|L|¬i|¬n|¬c|¬2|L|¬q|LPrepare 
 2536  to normalize the answer.>|L|L|¬j|¬m|¬p|L|¬n|¬o|¬r|¬m|LNormal
 2540  ize, round, and exit.>|L|¬8|¬h|L|¬e|¬q|¬u|L|¬1|≤#|¬1|¬.|¬1|≤
 2544  &>|L|¬w|¬m|¬1|L|¬c|¬o|¬n|L|¬8|¬b|≤*/|¬1|¬,|¬8|¬b|≤*/|¬1|≤#|¬1|
 2545  ¬.|¬4|≤&|LWord size minus one>{A3}|≡1|≡6|≡.|9|4If 
 2550  |ε|¬Gc|¬G|4|¬R|4|¬Gd|¬G, |πthen set |εr|4|¬L|4d|4|↔n|4c, 
 2554  s|4|¬L|4c|4|↔V (r|4|↔N|4d); x|4|¬L|4{H11}({H9}a|4|↔V|4(b|4|↔
 2556  N|4r){H11}){H9}|4|↔n|4s; y|4|¬L|4{H11}({H9}b|4|↔B|4(a|4|↔N|4
 2557  r){H11}){H9}|4|↔n|4s. |πOtherwise set |εr|4|¬L|4c|4|↔n|4d, 
 2561  s|4|¬L|4d|4|↔V|4(r|4|↔N|4c); x|4|¬L|4{H11}({H9}(a|4|↔N|4r)|4
 2562  |↔V|4b{H11}){H9}|4|↔n|4s, y|4|¬L|4{H11}({H9}(b|4|↔N|4r)|4|↔B
 2563  |4a{H11}){H9}|4|↔n|4s. |πThen |εx|4α+↓|4iy |πis 
 2567  the desired approximation to |ε(a|4α+↓|4bi)/(c|4α+↓|4di). 
 2572  [CACM |≡5 (1963), 435.] |πOther algorithms for 
 2579  complex arithmetic and function evaluation are 
 2585  given by P. Wynn, |εBIT |≡2 (1962), 232<255; 
 2593  |πsee also Paul Friedland, |εCACM |≡1|≡0 (1967), 
 2600  665.|'{A3}|π|≡1|≡7|≡.|9|4See Robert Morris, |εIEEE 
 2605  Transactions |π|≡C|≡-|≡2|≡0 (1971), 1578<1579. 
 2609  Error analysis is more di∃cult with such systems, 
 2617  so internal arithmetic is correspondingly more 
 2623  desirable.|'{A3}|≡1|≡8|≡.|9|4For positive numbers: 
 2627  shift fraction left until |εf|β1|4α=↓|41, |πthen 
 2633  round, then if the fraction is zero (rounding 
 2641  over⊗ow) shift it right again. For negative numbers: 
 2649  shift fraction left until |εf|β1|4α=↓|40, |πthen 
 2655  round, then if the fraction is zero (rounding 
 2663  under⊗ow) shift it right again.|'{A3}|≡1|≡9|≡.|9|4{H11}({H9}
 2668  43|4α+↓|4(1 if |εe|βv|4|¬W|4e|βu)|4α_↓|4(1 |πif 
 2672  fraction over⊗ow)|4α_↓N4(*?*?{A3}|≡1|≡9|≡.|9|4{H11}({H9}43|4α+
 2673  ↓|4(1 if |εe|βv|4|¬W|4e|βu)|4α_↓|4(1 |πif fraction 
 2678  over⊗ow)|4α_↓|4(10 if result zero)|4α+↓|4(4 if 
 2683  magnitude is rounded up)|4α+↓|4(1 if _rst rounding 
 2690  digit is |εb/2)|4α+↓|4(5 |πif rounding digits 
 2696  are |εW|β2|40|4.|4.|4.|40)|4α+↓|4(7 |πif rounding 
 2700  over⊗ow)|4α+↓|47|εN|4α+↓|4A(|→α_↓1|4α+↓|4(11 
 2701  |πif |εN|4|¬Q|40)){H11}){H9}u, |πwhere |εN |πis 
 2706  the number of left shifts during normalization, 
 2713  |εA|4α=↓|41 |πif rX receives nonzero digits (otherwise 
 2720  |εA|4α=↓|40). |πThe maximum time of |ε73u |πoccurs 
 2727  for example when |εu|4α=↓|4↓α+↓50|401|400|400|400, 
 2731  v|4α=↓|4|→α_↓46|449|499|499|499, b|4α=↓|4100. 
 2733  |π[The average time, considering the statistical 
 2739  data in Section 4.2.4, will be about 45|f1|d32|)|εu.]|'
 2747  {A3}{A22}{H10L12}|π|∨S|∨E|∨C|∨T|∨I|∨O|∨N|9|∨4|∨.|∨2|∨.|∨2|'
 2748  {A11}{H9L11}|9|1|≡1|≡.|9|4|εu|4|↔B|4v|4α=↓|4u|4|↔V|4|→α_↓v|4
 2748  α=↓|4|→α_↓v|4|↔V|4u|4α=↓|4|→α_↓(v|4|↔V|4|→α_↓u)|4α=↓|4|→α_↓(
 2748  v|4|↔B|4u).|'{A3}|9|1|≡2|≡.|9|4u|4|↔V|4x|4|¬R|4u|4|↔V|40|4α=
 2749  ↓|4u, |πby (8), (2), (6); hence by (8) again, 
 2758  |ε(u|4|↔V|4x)|4|↔V|4v|4|¬R|4u|4|↔V|4v. |πSimilarly, 
 2760  (8) and (6) together with (2) imply that |ε(u|4|↔V|4x)|4|↔V|
 2768  4(v|4|↔V|4y)|4|¬R|4(u|4|↔V|4x)|4|↔V|4v.|'{A3}|π|9|1|≡3|≡.|9|
 2769  4|εu|4α=↓|48.0000001, v|4α=↓|41.2500008, w|4α=↓|48.0000008; 
 2772  (u|4|↔N|4v)|4|↔N|4w|4α=↓|480.000064, u|4|↔N|4(v|4|↔N|4w)α=↓|
 2773  480.000057.|'{A3}|π|9|1|≡4|≡.|9|4Yes, let 1/|εu|4|¬V|4v|4α=↓
 2776  |4w |πwhere |εv |πis large.|'{A3}|9|1|≡5|≡.|9|4Not 
 2782  always; in decimal arithmetic take |εu|4α=↓|4v|4α=↓|49.|'
 2788  {A3}|π|9|1|≡6|≡.|9|4(a) Yes. (b) Only for |εb|4α+↓|4p|4|¬E|4
 2793  4 |π(try |εu|4α=↓|41|4α_↓|4b|gα_↓|gp). |π[W. 
 2797  M. Kahar observes that the identity |εdoes |πhold 
 2805  whenever |εb|gα_↓|g1|4|¬E|4f|βu|4|¬E|4b|gα_↓|g1|g/|g2. 
 2807  |πIt follows that 1|4|↔n|4{H11}({H9}1|4|↔n|4(1|4|↔n|4|εu){H1
 2810  1}){H9}|4α=↓|41|4|↔n|4|εu |πfor all |εu.]|'{A3}|9|1|≡7|≡.|9|
 2814  4|πIf |εu |πand |εv |πare consecutive ⊗oating-binary 
 2821  numbers, |εu|4|↔V|4v|4α=↓|42u |πor |ε2v. |πWhen 
 2826  it is |ε2v |πwe often ha¬e |εu|=|g|*2`|g2|4|↔V|4v|=|g|*2`|g2|4
 2832  |¬W|42v|=|g|*2`|g2. |πFor example, |εu|4α=↓|4.10|4.|4.|4.|400
 2835  1, v|4α=↓|4.10|4.|4.|4.|4010, u|4|↔V|4v|4α=↓|42v, 
 2838  u|=|g|*2`|g2|4|↔V|4v|=|g|*2`|g2|4α=↓|4.10|4.|4.|4.|4011.|'
 2839  {A3}|π|9|1|≡8|≡.|9|4(a) |→|¬Z, |→|¬V; (b) |→|¬Z, 
 2844  |→|¬V; (c) |→|¬Z, |→|¬¬ (d) |→|¬Z; (e) |→|¬Z.|'
 2852  {A3}|9|1|≡9|≡.|9|4|ε|¬Gu|4α_↓|4w|¬G|4|¬E|4|¬Gu|4α_↓|4v|¬G|4α
 2852  +↓|4|¬Gv|4α_↓|4w|¬G |¬E |≤e|β1 |πmin|ε(b|ge|ru|gα_↓|gq, 
 2856  b|βe|mv|βα_↓|βq)|4α+↓|4|≤e|β2 |πmin|ε(b|βe|mv|βα_↓|βq, 
 2858  b|βe|mw|βα_↓|βq) |¬E |≤e|β1b|βe|mu|gα_↓|gq|4α↓|4|≤e|β2b|ge|r
 2860  w|gα_↓|gq |¬E (|≤e|β1 α+↓ |≤e|β2)|πmax|ε(b|ge|ru|gα_↓|gq, 
 2865  c|ge|rw|gα_↓|gq). |πThe result cannot be strengthened 
 2871  in general, since for example we might have |εe|βu 
 2880  |πvery small compared to both |εe|βv |πand |εe|βw, 
 2888  |πand this means |εu|4α_↓|4w |πmight be fairly 
 2895  large under kthe hypotheses.|'{A3}|≡1|≡0|≡.|9|4If 
 2900  |εb|4|¬Q|42, |πwe have |ε.a|β1|4.|4.|4.|4a|βp|βα_↓|β1a|βp|4|
 2903  ↔N|4.9|4.|4.|4.|499|4α=↓|4.a|β1|4.|4.|4.|4a|βp|βα_↓|β1(a|βp|
 2903  4α_↓|41) |πif we take |εa|βp|4|¬R|42; |πhere 
 2909  ``9'' stands for |εb|4α_↓|41. |πFurthermore, 
 2914  |ε.a|β1|4.|4.|4.|4a|βp|βα_↓|β1a|βp|4|↔N|41.0|4.|4.|4.|40|4α=
 2914  ↓|4.a|β1|4.|4.|4.|4a|βp|βα_↓|β10, |πso the multiplication 
 2918  is not monotone. But when |εb|4α=↓|42, |πthis 
 2925  argument can be extended to show that multiplication 
 2933  |εis |πmonotone; obviously the ``certain computer'' 
 2939  had |εb|4|¬Q|42.|'{A3}|π|≡1|≡1|≡.|9|4Without 
 2942  loss of generality, let |εx |πbe an integer, 
 2950  |ε|¬Gx|¬G|4|¬W|4b|gp. |πIf |εe|4|¬E|40 |πthen 
 2954  |εt|4α=↓|40. |πIf |ε0|4|¬W|4e|4|¬E|4p |πthen 
 2958  |εx|4α_↓|4t |πhas at most |εp|4α+↓|41 |πdigits, 
 2964  the least signi_cant being zero. If |εe|4|¬Q|4p 
 2971  |πthen |εx|4α_↓|4t|4α=↓|40. |π[The result holds 
 2976  also under the weaker hypothesis |ε|¬Gt|¬G|4|¬W|42b|ge.]|'
 2982  {A3}|π|≡1|≡2|≡.|9|4Assume that |εe|βu|4α=↓|4p, 
 2985  e|βv|4|¬E|40, u|4|¬Q|40. |πCase 1, |εu|4|¬Q|4b|gp|gα_↓|g1. 
 2990  |πCase (1b), |εw|4α=↓|4u, |¬Gv|¬G|4|¬E|4|f1|d32|). 
 2994  |πThen |εu|¬S|4α=↓|4u, v|¬S|4α=↓|40, u|¬C|4α=↓|4u, 
 2998  v|¬C|4α=↓|40. |πIf |ε|¬Gv|¬G|4α=↓|4|f1|d32|) 
 3001  |πand more general rounding is permitted we might 
 3009  also have |εu|¬S|4α=↓|4u|4|¬N1. |πCase (1c), 
 3014  |εw|4α=↓|4u|4α_↓|41, v|4|¬E|4|→α_↓|f1|d32|), 
 3016  e|βv|4α=↓|40. |πThen |εu|¬S|4α=↓|4u |πor |εu|4α_↓|41, 
 3021  v|¬S|4α=↓|4|→α_↓1, u|¬C|4α=↓|4u, v|¬C|4α=↓|4|→α_↓1 
 3024  |πor 0. Case 2, |εu|4α=↓|4b|gp|gα_↓|g1. |πCase 
 3030  (2a), |εw|4α=↓|4u|4α+↓|41, v|4|¬R|4|f1|d32|), 
 3033  e|βv|4α=↓|40. |πLike (1a). Case (2b), |εw|4α=↓|4u, 
 3039  |¬Gv|¬G|4|¬e|4|f1|d32|), u|¬S|4|¬R|4u. |πLike 
 3042  (1b). Case (2c), |εw|4α=↓|4u, |¬Gv|¬G|4|¬E|4|f1|d32|), 
 3047  u|¬S|4|¬W|4u. |πThen |εu|¬S|4α=↓|4u|4α_↓|4j/b 
 3050  |πwhere |εv|4α=↓|4j/b|4α+↓|4v|β1 |πand |ε|¬Gv|β1|¬G|4|¬E|4|f
 3053  1|d32b|gα_↓|g1 |πfor some positive integer |εj|4|¬E|4|f1|d32
 3058  |)b; |πwe have |εv|¬S|4α=↓|40, u|¬C|4α=↓|4u, 
 3063  v|¬C|4α=↓|4j/b. |πCase (2d), |εw|4|¬W|4u. |πThen 
 3068  |εw|4α=↓|4u|4α_↓|4j/b |πwhere |εv|4α=↓|4|→α_↓j/b|4α+↓|4v|β1 
 3071  |πand |ε|¬Gv|β1|¬G|4|¬E|4|f1|d32|)b|gα_↓|g1 |πfor 
 3074  some positive integer |εj|4|¬E|4b; |πwe have 
 3080  |ε(v|¬S,|4u|¬C)|4α=↓|4(|→α_↓j/b,|4u), |πand |ε(u|¬S,|4v|¬C)|
 3082  4α=↓|4(u,|4|→α_↓j/b) |πor |ε(u|4α_↓|41/b, (1|4α_↓|4j)/b{H11}
 3085  ){H9}, |πthe latter case only when |εv|β1|4α=↓|4|f1|d32|)b|g
 3091  α_↓|g1. |πIn all cases |εu|4|↔B|4u|¬S|4α=↓|4u|4α_↓|4u|¬S, 
 3096  v|4|↔B|4v|¬S|4α=↓|4v|4α_↓|4v|¬S, u|4|↔B|4u|¬S|4α=↓|4u|4α_↓|4
 3097  u|¬C, v|4|↔B|4v|¬C|4α=↓|4v|4α_↓|4v|¬C, |πround|ε(w|4α_↓|4u|4
 3099  α_↓|4v)|4α=↓|4w|4α_↓|4u|4α_↓|4v.|'{A3}|π|≡1|≡3|≡.|9|4Since 
 3101  round|ε(x)|4α=↓|40 |πi= |εx|4α=↓|40, |πwe want 
 3106  to determine which integers |εm, n |πhave the 
 3114  property that |εm|4|↔n|4n |πis an integer i= 
 3121  |εm/n |πis. |πAssume that |ε|¬Gm|¬G, |¬Gn|¬G|4|¬W|4b|gp. 
 3127  |πIf |εm/n |πis an integer then |εm|4|↔n|4n|4α=↓|4m/n 
 3134  |πis also. Conversely if |εm/n |πis not an integer, 
 3143  but |εm|↔nn |πis, we have |ε1/|¬Gn|¬G|4|¬E|4|¬Gm|↔nn|4α_↓|4m
 3148  /n|¬G|4|¬E|4|f1|d32|)|4|¬Gm/n|¬G|4b|g1|gα_↓|gp, 
 3149  |πhence |ε|¬Gm|¬G|4|¬R|42b|gp|gα_↓|g1. |πOur 
 3152  answer is therefore to require |ε|¬Gm|¬G|4|¬W|42b|gp|gα_↓|g1
 3157   |πand |ε0|4|¬W|4|¬Gn|¬G|4|¬W|4b|gp. |π(Slightly 
 3161  weaker hypotheses are also possible.)|'{A3}|π|≡1|≡4|≡.|9|4|ε
 3166  |¬G(u |↔N v) |↔N w α_↓ uvw|¬G |¬E |¬G(u |↔N v) 
 3177  |↔N w α_↓ (u |↔N v)w|¬G α+↓ |¬Gw|¬G |¬Gu |↔N 
 3187  v α_↓ uv|¬G |¬E |≤d|β(|βu|β|↔N|βv|β)|β|↔N|βw 
 3192  α+↓ b|ge|rw|gα_↓|gq|gα_↓|g1|rw|≤d|βu|β|↔N|βv 
 3194  |¬E (1 α+↓ b)|4|≤d|β(|βu|β|↔N|βv|β)|β|↔N|βw. 
 3198  |πNow |ε|¬Ge|β(|βu|β|↔N|βv|β)|β|↔N|βw α_↓ e|βu|β|↔N|β(|βv|β|
 3201  ↔N|βw|¬G |¬E 2, |πso we may take |ε|≤e α=↓ |f1|d32|)(1 
 3211  α+↓ b)b|g2|gα_↓|gp.|'{A3}|π|≡1|≡5|≡.|9|4|εu|4|¬E|4v 
 3214  |πimplies that |ε(u|4|↔V|4u)|4|↔n|42|4|¬E|4(u|4|↔V|4v)|4|↔n|
 3216  42|4|¬E|4(v|4|↔V|4v)|4|↔n|42, |πso the condition 
 3220  holds for all |εu |πand |εv |πi= it holds whenever 
 3230  |εu|4α=↓|4v. |πFor base |εb|4α=↓|42, |πthe condition 
 3236  is therefore always satis_ed (barring over⊗ow); 
 3242  but for |εb|4|¬Q|42 |πthere are numbers |εv|4|=|↔6α=↓|4w 
 3249  |πsuch that |εv|4|↔V|4v|4α=↓|4w|4|↔V|4w, |πhence 
 3253  the condition fails. [On the other hand, the 
 3261  formula |εu|4|↔V|4{H11}({H9}(v|4|↔B|4u)|4|↔n|42{H11}){H9} 
 3263  |πdoes give a midpoint in the correct range. 
 3271  |εProof|*/:|\ |πIt su∃ces to show that |εu|4α+↓|4(v|4|↔B|4u)|
 3277  4|↔n|42|4|¬E|4v, |πi.e., |ε(v|4|↔B|4u)|4|↔n|42|4|¬E|4v|4α_↓|
 3279  4u; |πand it is easy to verify that round{H11}({H9}|f1|d32|)
 3287   round|ε(x){H11}){H9}|4|¬E|4x |πfor all |εx|4|¬R|40.]|'
 3292  {A3}|π|≡1|≡6|≡.|9|4(a) Exponent changes occur 
 3296  at |¬K|β1|β0|4α=↓|411.111111, |¬K|β9|β1|4α=↓|4101.11111, 
 3299  |¬K|β9|β0|β1|4α=↓|41001.1102, |¬K|β9|β0|β0|β1|4α=↓|410001.02
 3300  0, |¬K|β9|β0|β0|β0|β9|4α=↓|4100000.91, |¬K|β9|β0|β0|β8|β1|β9
 3302  |4α=↓|41000000.0; |¬K|β1|β0|β0|β0|β0|β0|β0|4α=↓|41109099.1. 
 3304  (b) |¬K|ε|β1|β|¬E|βk|β|¬E|βn|41.2345679|4α=↓|41224782.1, 
 3306  |πand (14) tries to take the square root of |→α_↓.0053187053
 3315  . But (15) and (16) are exact in this case. [If 
 3326  |εx|βk|4α=↓|41|4α+↓|4|"l(k|4α_↓|41)/2|"L10|gα_↓|g7, 
 3327  |π(15) and (16) have errors of order |εn.] (c) 
 3336  |πBasically we need to show that |εu|4|↔V|4(v|4|↔B|4u)|4|↔n|
 3342  4k |πlies between |εu |πand |εv; |πsee exercise 
 3350  15.|'{A3}|h|≡1|≡7|≡.|9|4|∂|¬f|¬c|¬m|¬p!|∂|¬c|¬m|¬p|¬a!|∂|≡e|
 3351  ≡p|≡s|≡i|≡l|≡o|≡n|≤#|¬1|¬.|¬5|≤&!!|∂Make rA nonzero 
 3354  with same sign.|E|n|'|≡1|≡7|≡.|9|4|L|¬f|¬c|¬m|¬p|L|¬s|¬t|¬j|
 3357  L|¬9|¬f|LFloating point comparison subroutine:>
 3361  |L|L|¬j|¬o|¬v|L|¬o|¬f|¬l|¬o|LEnsure over⊗ow is 
 3364  o=.>|L|L|¬s|¬t|¬a|L|¬t|¬e|¬m|¬p>|L|L|¬l|¬d|¬a|¬n|L|¬t|¬e|¬m|
 3366  ¬p|L|εv|4|¬L|4|→α_↓v.|π>!|9|7(Copy here lines 
 3370  07-20 of Program 4.2.1A.)|'|L|L|¬l|¬d|¬x|L|¬f|¬v|≤#|¬0|¬.|¬0
 3374  |≤&|LSet rX to zero with sign of |εf|βv.|π>|L|L|¬d|¬e|¬c|¬1|
 3382  L|¬5>|¬j|¬1|¬n|Lα/↓|≤%|¬2>|L|L|¬e|¬n|¬t|¬1|L|¬0|LReplace 
 3385  large di=erence in exponents>|L|L|¬s|¬r|¬a|¬x|L|¬5|¬,|¬1|L!b
 3389  y a smaller one.>|L|L|¬a|¬d|¬d|L|¬f|¬u|LrA|4|¬L|4di=erence 
 3394  of operands.>|L|L|¬j|¬o|¬v|L|¬7|¬f|LFraction 
 3397  over⊗ow: not |→|¬Z.>|L|L|¬c|¬m|¬p|¬a|L|¬e|¬p|¬s|¬i|¬l|¬o|¬n|
 3400  ≤#|¬1|¬.|¬5|≤&>|L|L|¬j|¬g|L|¬8|¬f|LJump if not 
 3404  |→|¬Z.>|L|L|¬j|¬l|L|¬6|¬f|LJump if |→|¬Z.>|L|L|¬j|¬x|¬z|L|¬9
 3408  |¬f|LJump if |→|¬Z.>|L|L|¬j|¬x|¬p|L|¬1|¬f|LIf 
 3412  |¬GrA|¬G|4α=↓|4|ε|≤e, |πcheck sign of rA|4α⊗↓|4rX.>
 3417  |L|L|¬j|¬a|¬p|L|¬9|¬f|LJump if |→|¬Z. (rA|4|=|↔6α=↓|40)>
 3421  |L|L|¬j|¬m|¬p|L|¬8|¬f>|L|¬7|¬h|L|¬e|¬n|¬t|¬x|L|¬1>
 3423  |L|L|¬s|¬r|¬c|L|¬1|LMake rA nonzero with same 
 3428  sign.>|L|L|¬j|¬m|¬p|L|¬8|¬f>|L|¬1|¬h|L|¬j|¬a|¬p|L|¬8|¬f|LJum
 3430  p if not |→|¬Z. (rA|4|=|↔6α=↓|40)>|L|¬6|¬h|L|¬e|¬n|¬t|¬a|L|¬
 3435  0>|L|¬8|¬h|L|¬c|¬m|¬p|¬a|L|≤$|¬0|≤$|LSet comparison 
 3438  indicator.>|L|¬9|¬h|L|¬j|¬m|¬p|Lα/↓|LExit from 
 3441  subroutine.>|Hβ*?*?{U0}{H9L11M29}|π58320#Computer 
folio 742 galley 4
 3443  Programming!(Knuth/Addison-Wesley)!f. 742!Ans!g. 
 3445  4c|'{A6}|≡1|≡9|≡.|9|4|≡1|≡9|≡.|9|4Let |ε|≤g|βk|4α=↓|4|≤d|βk|
 3447  4α=↓|4|≤h|βk|4α=↓|4|≤s|βk|4α=↓|40 |πfor |εk|4|¬Q|4n. 
 3450  |πIt su∃ces to _nd the coe∃cient of |εx|β1, |πsince 
 3459  the coe∃cient of |εx|βk |πwill be the same except 
 3468  with all subscripts increased by |εk|4α_↓|41. 
 3474  |πLet |ε(f|βk,|4g|βk) |πdenote the coe∃cient 
 3479  of |εx|β1 |πin |ε(s|βk|4α_↓|4c|βk,|4c|βk) |πrespectively. 
 3484  Then |εf|β1|4α=↓|4(1|4α+↓|4|≤h|β1)(1|4α_↓|4|≤g|β1|4α_↓|4|≤g|
 3485  β1|≤d|β1|4α_↓|4|≤g|β1|≤s|β1|4α_↓|4|≤d|β1|≤s|β1|4α_↓|4|≤g|β1|
 3485  4|≤d|β1|≤s|β1), g|β1|4α=↓|4(1|4α+↓|4|≤d|β1)(1|4α+↓|4|≤h|β1)(
 3486  |≤g|β1|4α+↓|4|≤s|β1|4α+↓|4|≤g|β1|≤s|β1), |πand 
 3488  |εf|βk|4α=↓|4(1|4α_↓|4|≤g|βk|≤s|βk|4α_↓|4|≤d|βk|≤s|βk|4α_↓|4
 3488  |≤g|βk|≤d|βk|≤s|βk)f|βk|βα_↓|β1|4α+↓|4(|≤g|βk 
 3489  α_↓ |≤h|βk α+↓ |≤g|βk|4|≤d|βk α+↓ |≤g|βk|≤h|βk 
 3495  α+↓ |≤g|βk|4|≤d|βk|≤h|βk α+↓ |≤g|βk|≤h|βk|≤s|βk 
 3499  α↓ |≤d|βk|≤h|βk|≤s|βk α+↓ |≤g|βk|4|≤d|βk|≤h|βk|≤s|βk)g|βk|βα
 3502  _↓|β1, g|βk α=↓ |≤s|βk(1 α+↓ |≤g|βk)(1 α+↓ |≤d|βk)f|βk|βα_↓|
 3509  β1 α_↓ (1 α+↓ |≤d|βk(|≤g|βk α+↓ |≤g|βk|≤h|βk 
 3516  α+↓ |≤h|βk|≤s|βk α+↓ |≤g|βk|≤h|βk|≤s|βk)g|βk|βα_↓|β1, 
 3520  |πfor |ε1|4|¬W|4k|4|¬E|4n. |πThus |εf|βn α=↓ 
 3525  1 α+↓ |≤h|β1 α_↓ |≤g|β1 α+↓ (4n |πterms of 2nd 
 3535  order) α+↓ (higher order terms)|4α=↓|41|4α+↓|4|ε|≤h|β1|4α_↓|
 3539  4|≤g|β1|4α+↓|4O(n|≤e|g2) |πis su∃ciently small. 
 3543  [The Kahan summation formula was _rst published 
 3550  in |εCACM |≡8 (1965), 40; |πcf. |εProc. IFIP 
 3558  Congress (1971), |≡2|≡, 1232. |πFor another approach 
 3565  to accurate summation, see R. J. Hanson, |εCACM 
 3573  |≡1|≡8 (1975), 57<58.]|'{A3}|π|≡2|≡0|≡.|9|4By 
 3577  the proof of Theorem C, (47) fails for |εe|βw|4α=↓|4p 
 3586  |πonly if |ε|¬Gv|¬G|4α+↓|4|f1|d32|)|4|¬E|4|¬Fw|4α_↓|4u|¬G|4|
 3588  ¬R|4b|gp|gα_↓|g1|4α+↓|4b|gα_↓|g1; |πhence |ε|¬Gf|βu|¬G|4|¬R|
 3590  4|¬Gf|βv|¬G|4|¬R|41|4α_↓|4(|f1|d32|)b|4α_↓|41)b|gα_↓|gp. 
 3591  |πThis rather rare case, in which |ε|¬Gf|βw|¬G 
 3598  |πbefore normalization takes its maximum value 
 3604  2, is necessary and su∃cient.|'{A3}|π|≡2|≡1|≡.|9|4(Solution 
 3610  by G. W. Veltkamp.) Let |εc|4α=↓|42|g|"p|gp|g/|g2|g|"P|4αt↓|
 3615  41; |πwe may assume that |εp|4|¬E|42, |πso |εc 
 3623  |πis redpresentable. First compute |εu|¬S|4α=↓|4u|4|↔N|4c, 
 3628  u|β1|4α=↓|4(u|4|↔B|4u|¬S)|4|↔V|4u|¬S, u|β2|4α=↓|4u|4|↔B|4u|β
 3629  1; v|¬S|4α=↓|4v|4|↔N|4c, v|β1|4α=↓|4(v|4|↔B|4v|¬S)|4|↔V|4v|¬
 3631  S, v|β2|4α=↓|4v|4|↔B|4v|β1. |πThen set |εw|4|¬L|4u|4|↔N|4v, 
 3636  w|¬S|4|¬L|4{H11}({H9}((u|β1|4|↔N|4v|β1|4B|4w)|4|↔V|4(u|β1|4|
 3636  ↔N|4v|β2))|4|↔V|4(u|β2|4|↔N|4v|β1){H11}){H9}|4|↔V|4(u|β2|4|↔
 3636  N|4v|β2).|'|π!!|2It su∃ces to prove this when 
 3643  |εu, v|4|¬Q|40 |πand |εe|βu|4α=↓|4e|βu|4α=↓|4p, 
 3647  |πao that |εu |πand |εv |πare integers|4|¬A|4[|ε2|gp|gα_↓|g1
 3653  ,|42|gp). |πThen |εu|4α=↓|4u|β1|4α+↓|4u|β2 |πwhere 
 3657  |ε2|gp|gα_↓|g1|4|¬E|4u|β1|4|¬E|42|gp, u|β1|4|πmod|4|ε2|g|"p|
 3658  gp|g/|g2|"P|4α=↓|40, |πand |ε|¬Gu|β2|¬G|4|¬E|42|g|"p|gp|g/|g
 3660  2|g|"P|gα_↓|g1; |πsimilarly |εv|4α=↓|4v|β1|4α↓|4v|β2. 
 3663  |πThe operations during the calculation of |εw|¬S 
 3670  |πare exact, because |εw|4α_↓|4u|β1v|β1 |πis 
 3675  a multiple of 2|ε|gp|gα_↓|g1 |πwith |ε|¬Gw|4α_↓|4u|β1v|β1|¬G
 3680  |4|¬E|4|¬Gw|4α_↓|4uv|¬G|4α+↓|4|¬Gu|β2v|β1|4α+↓|4u|β1v|β2|4αt
 3680  ↓|4u|β2v|β2|¬G|4|¬E|42|gp|gα_↓|g1|4α↓|42|gp|gα+↓|g|"p|gp|g/|
 3680  g2|g|"P|4αt↓|42|gp|gα_↓|g1; |πand |ε|¬Gw|4α_↓|4u|β1v|β1|4α_↓
 3682  |4u|β1v|β2|¬G|4|¬E|4|¬Gw|4α_↓|4uv|¬G|4α↓|4|¬Gu|β2v|¬G|4|¬W|4
 3682  2|gp|gα_↓|g1|4α+↓|42|g|"p|gp|g/|g2|g|"P|gα_↓|g1|gα+↓|gp, 
 3683  |πwhere |εw|4α_↓|4u|β1v|β1|4α_↓|4u|β1v|β2 |πis 
 3686  a multiple of |ε2|g|"p|gp|g/|g2|g|"P.|'|π|≡2|≡2|≡.|9|4We 
 3691  may assume that |εb|gp|gα_↓|g1|4|¬E|4u, v|4|¬W|4b|gp. 
 3696  |πIf |εuv|4|¬E|4b|g2|gp|gα_↓|g1 |πthen |εx|β1|4α=↓|4uv|4α_↓|
 3699  4r |πwhere |ε|¬Gr|¬G|4|¬E|4|f1|d32|)b|gp|gα_↓|g1, 
 3702  |πhence |εx|β2|4α=↓|4|πround|ε(u|4α_↓|4r/v)|4α=↓|4x|β0 
 3704  |π(since |ε|¬Gr/v|¬G|4|¬E|4|f1|d32|)b|gp|gα_↓|g1/b|gp|gα_↓|g
 3705  1|4|¬E|4|f1|d32|), |πand equality implies |εv|4α=↓|4b|gp|gα_
 3709  ↓|g1 |πhence |εr|4α=↓|40). |πIf |εuv|4|¬Q|4b|g2|gp|gα_↓|g1 
 3714  |πthen |εx|β1|4α=↓|4uv|4α_↓|4r |πwhere |ε|¬gr|¬g|4|¬E|4|f1|d
 3717  32|)b|gp, |πhence |εx|β1/v|4|¬E|4u|4α_↓|4r/v|4|¬W|4b|gp|4α+↓
 3719  |4|f1|d32|)b |πand |εx|β2|4|¬E|4b|gp. |πIf |εx|β2|4α=↓|4b|gp
 3723   |πthen |εx|β3|4α=↓|4x|β1 |π(for otherwise |εb|gp|4α_↓|4|f1|
 3728  d32|))v|4|¬E|4x|β1|4|¬E|4b|gp(v|4α_↓|41)). |πIf 
 3730  |εx|β2|4|¬W|4b|gp |πand |εx|β1|4|¬Q|4b|g2|gp|gα_↓|g1 
 3733  |πthen let |εx|β2|4α=↓|4x|β1/v|4α+↓|4q |πwhere 
 3737  |ε|¬Gq|¬G|4|¬E|4|f1|d32|); |πwe have |εx|β3|4α=↓|4|πround|ε(
 3740  x|β1|4αt↓|4qv)|4α=↓|4x|β1. |πFinally if |εx|β2|4|¬W|4b|gp 
 3744  |πand |εx|β1|4α=↓|4b|g2|gp|gα_↓|g1 |πand |εx|β3|4|¬W|4b|g2|g
 3747  p|gα_↓|g1 |πthen |εx|β4|4α=↓|4x|β2 |πby the _rst 
 3753  case above. This situation arises e.g. for |εb|4α=↓|410, 
 3761  p|4α=↓|42, u|4α=↓|419, v|4α=↓|455, x|β1|4α=↓|41000, 
 3765  x|β2|4α=↓|418, x|β3|4α=↓|4990.|'{A9}|π|≡2|≡3|≡.|9|4Let 
 3768  |ε|"lu|"L|4α=↓|4n, |πso that |εu|4|πmod|41|4α=↓|4|εu|4|↔B|4n
 3771  |4α=↓|4u|4α_↓|4n|4α+↓|4r |πwhere |ε|¬Gr|¬G|4|¬E|4|f1|d32|)b|
 3773  gα_↓|gp; |πwe wish to show that round|ε(n|4α_↓|4r)|4α=↓|4n. 
 3780  |πThe result is clear if |ε|¬Gn|¬G|4|¬Q|41; |πand 
 3787  |εr|4α=↓|40 |πwhen |εn|4α=↓|40 |πor 1, so the 
 3794  only subtle case is when |εn|4α=↓|4|→α_↓1, r|4α=↓|4|f1|d32|)
 3800  b|gα_↓|gp. |πThe identity fails i= |εb |πis a 
 3808  multiple of 4 and |ε|→α_↓b|gα_↓|g1|4|¬W|4u|4|¬W|4|→α_↓b|gα_↓
 3812  |g2 |πand |εu|4|πmod|4|ε2b|gα_↓|gp|4α=↓|4|f3|d32|)b|gα_↓|gp 
 3815  |π(e.g., |εp|4α=↓|43, b|4α=↓|48, u|4α=↓|4|→α_↓.0124).|'
 3819  {A3}|π|≡2|≡4|≡.|9|4Let |εu|4α=↓|4[a,|4b], v|4α=↓|4[c,|4d]. 
 3822  |πThen |εu|4|↔V|4v|4α=↓|4[a|4{H11}|*2+{H9}|4c,|4b|4{H11}|*2∃{H
 3823  9}|4d] |πwhere {H11}|*2∃{H9} is commutative, |εx|4{H11}|*2∃{H9
 3828  }|410|4α=↓|4x |πfor all |εx, x|4{H11}|*2∃{H9}|4α_↓|40|4α=↓|4x
 3832   |πfor all |εx|4|=|↔6α=↓|4|→α+↓0, x|4{H11}|*2∃{H9}|4|→α+↓|→|¬
 3836  X|4α=↓|4|→α+↓|→|¬X |πfor all |εx, |πand |εx|4{H11}|*2∃{H9}|4|
 3841  →α_↓|→|¬X |πneed'nt be de_ned; |εx|4{H11}|*2+{H9}|4y|4α=↓|4|→
 3845  α_↓{H11}({H9}(|→α_↓x)|4{H11}|*2∃{H9} (|→α_↓y){H11}){H9}. 
 3847  |πAlso |εu|4|↔B|4v|4α=↓|4u|4|↔V|4(|→α_↓v) |πwhere 
 3850  |ε|→α_↓v|4α=↓|4[|→α_↓d,|4|→α_↓c].|'|π!!|2Let 
 3852  |εu|4|↔N|4v|4α=↓|4[|πmin(|εa|4{H11}|*2+{H9}|4c, 
 3853  a|4{H11}|*2+{H9}|4d, b|4{H11}|*2+{H9}|4c, b|4{H11}|*2+{H9}|4d),
 3855   |πmax(|εa|4{H11}|*2∃{H9}|4c, a|4{H11}|4|*2∃{H9}|4d, 
 3858  b|4{H11}|*2∃{H9}|4c, b|4{H11}|*2∃{H9}|4d)], |πwhere 
 3861  |εx|4{H11}|*2∃{H9}|4y|4α=↓|4y|4{H11}|*2∃{H9}x, 
 3862  x|4{H11}|*2∃{H9}|4(|→α_↓y)|4α=↓|4|→α_↓(x|4{H11}|*2+{H9}|4y)|4α
 3862  =↓|4(|→α_↓x)|4{H11}|*2∃{H9}|4y; x|4{H11}|*2∃{H9}|4|→α+↓0|4α=↓|
 3863  4|→α+↓0 |πfor |εx|4|¬Q|40, |→α_↓0 |πfor |εx|4|¬W|40; 
 3869  x|4{H11}|*2∃{H9}|4|→α_↓0|4α=↓|4|→α_↓(x|4{H11}|*2∃{H9}|4|→α+↓0)
 3869  ; x|4{H11}|*2∃{H9}|4|→α+↓|¬X|4α=↓|4|→α+↓|¬X |πfor 
 3872  |εx|4|¬Q|4|→α+↓0, |→α_↓|¬X|4|πfor |εx|4|¬W|4↓α_↓0. 
 3875  |π(It is possible to determine the min and max 
 3884  simply by looking at the signs of |π|εa, b, c, 
 3894  d, |πthereby computing only two of the eight 
 3902  products, except when |εa|4|¬W|40|4|¬W|4b |πand 
 3907  |εc|4|¬W|40|4|¬W|4d; |πin the latter case we 
 3913  compute four products and the answer is [min|ε(a|4{H11}|*2+{H
 3920  9}|4d, b|4{H11}|*2+{H9}|4c), |πmax|ε(a|4{H11}|*2∃{H9}|4c, 
 3923  b|4{H11}|*2∃{H9}|4d)].)|'!!|2Finally, |εu|4|↔n|4v 
 3926  |πis unde_ned if |εc|4|¬W|40|4|¬W|4d; |πotherwise 
 3931  we use the formulas for multiplication with |εc, 
 3939  d |πreplaced by |εd|gα_↓|g1, c|gα_↓|g1, |πwhere 
 3945  |εx|4{H11}|*2∃{H9}|4y|gα_↓|g1|4α=↓|4x|4{H11}|*2∃{H9}|4y, 
 3946  x|4{H11}|*2+{H9}|4y|gα_↓|g1|4α=↓|4x|4{H11}|*2+{H9}|4y, 
 3947  (|→|¬N0)|gα_↓|g1|4α=↓|4|→|¬N|¬X, (|→|¬N|¬X)|gα_↓|g1|4α=↓|4|→
 3948  |¬N0.|'{A3}|π|≡2|≡5|≡.|9|4Cancellation reveals 
 3951  |εprevious |πerrors in the computation of |εu 
 3958  |πand |εv. |πFor example, if |ε|≤es|πis small, 
 3965  we often get poor accuracy when computing |εf(x|4α+↓|4|≤e)|4
 3972  |↔B|4f(x), |πbecause the rounded calculation 
 3977  of |εf(x|4α+↓|4|≤e) |πdestroys much of the information 
 3984  about |ε|≤e. |πIt is often desirable to reunite 
 3992  such formulas as |ε|≤e|4|↔N|4g(x,|4|≤e), |πwhere 
 3997  |εg(x,|4|≤e)|4α=↓|4{H11}({H9}f(x|4α+↓|4|≤e)|4α_↓|4f(x){H11})
 3997  /|≤e |πis _rst computed symbolically. Thus, if 
 4004  |εf(x)|4α=↓|4x|g2 |πthen |εg(x,|4|≤e)|4α=↓|42x|4α+↓|4|≤e; 
 4007  |πif |εf(x)|4α=↓|4{H11}|¬H{H9}|v4x|) |πthen |εg(x,|4|≤e)|4α=
 4010  ↓|41/({H11}|¬H{H9}|v4x|4α+↓|4|≤e|)|4α+↓|4{H11}|¬H{H9}|v4x|))
 4010  .|'{A3}{A22}{H10L12}|π|∨S|∨E|∨C|∨T|∨I|∨O|∨N|9|∨4|∨.|∨2|∨.|∨3
 4011  |'{A11}{H9L11}|9|1|≡1|≡.|9|4First, |ε(w|βm,|4w|βi)|4α=↓|4(.5
 4013  73,|4.248); |πthen |εw|βmv|βl/v|βm|4α=↓|4.290; 
 4016  |πso the answer is (.572,|4.958). This in fact 
 4024  is the correct result to six decimals.|'{A3}|9|1|≡2|≡.|9|4Th
 4031  e answer is not a=ected, since the normalization 
 4039  routine truncates to eight places and can never 
 4047  look at this particular byte position. (Scaling 
 4054  to the left occurs at most once during normalization, 
 4063  since the inputs are normalized.)|'{A3}|9|1|≡3|≡.|9|4Over⊗ow
 4068   obviously cannot occur at line 09, since we 
 4077  are adding two-byte quantities, or at line 22, 
 4085  since we are adding four-byte quantities. In 
 4092  line 30 we are computing the sum of three four-byte 
 4102  quantities, so this cannot over⊗ow. Finally, 
 4108  in line 32, over⊗ow is impossible because the 
 4116  product |εf|βuf|βv |πmust be less than unity.|'
 4123  {A3}|9|1|≡4|≡.|9|4Insert ``|¬j|¬o|¬v |¬o|¬f|¬l|¬o|≤⊃ 
 4126  |¬e|¬n|¬t|¬1 |¬0'' between lines 03 and 04. Replace 
 4134  lines 21<22 by ``|¬a|¬d|¬d |¬t|¬e|¬m|¬p|≤#|¬a|¬b|¬s|≤&|≤⊃ 
 4139  |¬j|¬n|¬o|¬v α/↓|≤%|¬2|≤⊃ |¬i|¬n|¬c|¬1 |¬1'', 
 4143  and change lines 28<31 to ``|¬s|¬l|¬a|¬x |¬5|≤⊃ 
 4150  |¬a|¬d|¬d |¬t|¬e|¬m|¬p|≤⊃ |¬j|¬n|¬o|¬v α/↓|≤%|¬2|≤⊃ 
 4154  |¬i|¬n|¬c|¬1 |¬1|≤⊃ |¬e|¬n|¬t|¬x |¬0|¬, |¬2|≤⊃ 
 4159  |¬s|¬r|¬c |¬5''. This odds _ve lines of code 
 4167  and only 1, 2, or 3 units of execution time.|'
 4177  {A3}|9|1|≡5|≡.|9|4Insert ``|¬j|¬o|¬v |¬o|¬f|¬l|¬o'' 
 4180  after line 06. Change lines 22, 31, 39 respectively 
 4189  to |¬s|¬r|¬a|¬x |¬0, |¬1|≤⊃ |¬s|¬l|¬a|¬x |¬5|≤⊃ 
 4195  |¬a|¬d|¬d |¬a|¬c|¬c. Between lines 40 and 41, 
 4202  insert ``|¬d|¬e|¬c|¬2 |¬1|≤⊃ |¬j|¬n|¬o|¬v |¬d|¬n|¬o|¬r|¬m|≤⊃
 4206   |¬i|¬n|¬c|¬2 |¬1|≤⊃ |¬i|¬n|¬c|¬x |¬1|≤⊃ |¬s|¬r|¬c 
 4212  |≤⊃''. [It's tempting to remove the |¬d|¬e|¬c 
 4219  |¬1 in factor of |¬s|¬t|¬z |¬e|¬x|¬p|¬o, but 
 4226  then |¬i|¬n|¬c|¬2 |¬1 might over⊗ow vI2*3] This 
 4233  adds six lines of code; the time |εdecreases 
 4241  b|πby |ε3u |πunless there is fraction over⊗ow, 
 4248  when it increases by |ε7u.|'{A3}|9|1|≡6|≡.|E|'
 4254  |h|≡6|≡.|9|4|∂|¬d|¬o|¬u|¬b|¬l|¬e!|∂|¬s|¬l|¬a|¬x!|∂|¬t|¬e|¬m|
 4254  ¬p|≤#|¬e|¬x|¬p|¬d|≤&!!|∂Correct for di=erence 
 4257  in excess.|'|h|n|'|∂|¬d|¬o|¬u|¬b|¬l|¬e|L|¬s|¬t|¬j|L|¬e|¬x|¬i
 4260  |¬t|¬d|¬f|LConvert to double precision:>|L|L|¬e|¬n|¬t|¬x|¬0|
 4264  LClear rX.>|L|L|¬s|¬t|¬a|L|¬t|¬e|¬m|¬p>|L|L|¬l|¬d|¬2|L|¬t|¬e
 4267  |¬m|¬p|≤#|¬e|¬x|¬p|≤&|LrI2|4|¬L|4|εe.>|L|L|π|¬i|¬n|¬c|¬2|L|¬
 4268  q|¬q|≤*/|¬q|LCorrect for di=erence in excess.>
 4273  |L|L|¬s|¬t|¬z|L|¬e|¬x|¬p|¬o|L|¬e|¬x|¬p|¬o|4|¬L|40.>
 4274  |L|L|¬s|¬l|¬a|¬x|L|¬1|LRemove exponent.>|L|L|¬j|¬m|¬p|L|¬d|¬
 4276  n|¬o|¬r|¬m|LNormalize and exit.>|L|¬s|¬i|¬n|¬g|¬l|¬e|L|¬s|¬t
 4279  |¬j|L|¬e|¬x|¬i|¬t|¬f|LConvert to single precision:>
 4283  |L|L|¬j|¬o|¬v|L|¬o|¬f|¬l|¬o|LEnsure over⊗ow is 
 4286  o=.>|L|L|¬s|¬t|¬a|L|¬t|¬e|¬m|¬p>|L|L|¬l|¬d|¬2|L|¬t|¬e|¬m|¬p|
 4288  ≤#|¬e|¬x|¬p|¬d|≤&|LrI2|4|¬L|4|εe.>|π|L|L|¬d|¬e|¬c|¬2|¬q|¬q|≤
 4289  */|¬q|LCorrect for di=erence in excess.>|L|L|¬s|¬l|¬a|¬x|L|¬2
 4294  |LRemove exponent.>|L|L|¬j|¬m|¬p|L|¬n|¬o|¬r|¬m|LNormalize, 
 4297  round, and exit.>{A3}|9|1|≡7|≡.|9|4All three 
 4302  routines give zero as the answer if and only 
 4311  if the exact result would be zero, so we need 
 4321  not worry about zero denominators in the expressions 
 4329  for relative error. The worst case of the addition 
 4338  rotuine is pretty bad: Visualized in decimal 
 4345  notation, if the inputs are 1.0000000 and .99999999, 
 4353  the answer is |εb|gα_↓|g7 |πinstead of |εb|gα_↓|g8: 
 4360  |πthus the maximum relative error |ε|≤d|β1 |πis 
 4367  |εb|4α_↓|41, |πwhere |εb |πis the byte size.|'
 4374  For multiplication and division, we may assume 
 4381  that the exponents of both operands are |¬q|¬q, 
 4389  and that both operands are positive. The maximum 
 4397  error in multiplication is readily bounded by 
 4404  considering Fig. 4: When |εuv|4|¬R|41/b, |πwe 
 4410  have 0|4|¬E|4uv|4α_↓|4u|4|↔N|4v|4|¬W|43b|gα_↓|g9|4α+↓|4(b|4α
 4411  _↓|41)b|gα_↓|g9, |πso the relative error is bounded 
 4418  by (|εb|4α↓|42)b|gα_↓|g8. |πWhen 1/|εb|g2|4|¬E|4uv|4|¬W|41/b
 4421  , |πwe have 0|4|¬E|4uv|4α_↓|4u|4|↔N|4v|4|¬W|43b|gα_↓|g9, 
 4425  |πso the relative error in this case is bounded 
 4434  by 3|εb|gα_↓|g9/uv|4|¬E|43b|gα_↓|g7. |πWe take 
 4438  |ε|≤d|β2 |πto be the larger of the two estimates, 
 4447  namely |ε3b|gα_↓|g7.|'|π!!|2Division requires 
 4451  a more careful analysis of Program D. The quantity 
 4460  actually computed by the subroutine is |ε|≤a|4α_↓|4|≤d|4α_↓|
 4466  4b|≤e{H11}({H9}(|≤a|4α_↓|4|≤d|¬C)(|≤b|4α_↓|4|≤d|¬S)|4α_↓|4|≤
 4466  d|1|9{H11}){H9}|4α_↓|4|≤d|βn |πwhere |ε|≤a|4α=↓|4(u|βm|4α↓|4
 4468  |≤eu|βl)/bv|βm, |≤b|4α=↓|4v|βl/bv|βm, |πand |ε|≤d, 
 4472  |≤d|¬S, |≤d|¬C, |≤d|9|1, |≤d|βn |πare nonnegative 
 4478  truncation errors with |ε|≤d|4|¬W|4b|gα_↓|g1|g0, 
 4482  |≤d|¬S|4|¬W|4b|gα_↓|g5, |≤d|¬C|4|¬W|4b|gα_↓|g5, 
 4484  |≤d|9|1|4|¬W|4b|gα_↓|g6, |πand |ε|≤d|βn |π(which 
 4488  occurs during normalization) is either less than 
 4495  |εb|gα_↓|g9 |πor |εb|gα_↓|g8 |πdepending on whether 
 4501  scaling occurs or not. The actual value of the 
 4510  quotient is |ε|≤a/(1|4α↓|4b|≤e|≤b)|4α=↓|4|≤a|4α_↓|4b|≤e|≤a|≤
 4512  b|4α↓|4b|g2|≤a|≤b|g2|≤d|¬C|¬C, |πwhere |ε|≤d|¬C|¬C 
 4515  |πis the nonnegative error due to truncatioon 
 4522  of the in_nite series (3); |ε|≤d|¬C|¬C|4|¬W|4|≤e|g2, 
 4528  |πsince it is an alternating series. The relative 
 4536  error is therefore the absolute value of |ε(b|≤e|≤d|¬S|4α↓|4
 4543  b|≤e|≤d|¬C|≤b/|≤a|4α↓|4b|≤e|≤d|9|1/|≤a)|4α_↓|4(|≤d/|≤a|4α↓|4
 4543  b|≤e|≤d|¬S|≤d|¬C/|≤a|4α↓|4b|g2|≤b|g2|≤d|¬C|¬C|4α+↓|4|≤d|βn/|
 4543  ≤a), |πtimes |ε(1|4α↓|4b|≤e|≤b). |πThe positive 
 4548  terms in this expression are bounded by |εb|gα_↓|g9|4α↓|4b|g
 4555  α_↓|g8|4α↓|4b|gα_↓|g8, |πand the negative terms 
 4560  are bounded by |εb|gα_↓|g8|4α↓|4b|gα_↓|g1|g2|4α↓|4b|gα_↓|g8 
 4564  |πplus the contribution by the normalizing phase, 
 4571  which can be about |εb|gα_↓|g7 |πin magnitude. 
 4578  It is therefore clear that the potentially greatest 
 4586  part of the relative error comes during the normalization 
 4595  phase, and that |ε|≤d|β3|4α=↓|4(b|4α↓|42)b|gα_↓|g8 
 4599  |πis a safe upper bound for the relative error.|'
 4608  {A3}|9|1|≡8|≡.|9|4Addition: If |εe|βu|4|¬E|4e|βv|4α↓|41, 
 4611  |πthe entire relative error occurs during the 
 4618  normalization phase, so it is bounded above by 
 4626  |εb|gα_↓|g7. |πIf |εe|βu|4|¬R|4e|βv|4α+↓|42, 
 4629  |πand it the signs are the same, again the entire 
 4639  error may be ascribed to normalization; if the 
 4647  signs are opposite, the error due to shifting 
 4655  digits out of the register is in the opposite 
 4664  direction from the subsequent error introduced 
 4670  during normalization. Both of these errors are 
 4677  bounded by |εb|gα_↓|g7, |πhence |ε|≤d|β1|4α=↓|4b|gα_↓|g7. 
 4682  |π(This is substantially better then the result 
 4689  in exercise 7*3)|'!!|2Multiplication: An analysis 
 4695  as in {U0}{H9L11M29}|π58320#Computer Programming!(Knuth/Addi
folio 748 galley 5
 4698  son-Wesley)!Ans!f. 748!g. 5|'{A23}{H10L12}|∨S|∨E|∨C|∨T|∨I|∨O
 4701  |∨N|9|∨4|∨.|∨2|∨.|∨4|'{A11}{H9L11}|9|1|≡1|≡.|9|4Since 
 4703  fraction over⊗ow can occur only when the operands 
 4711  have the same sign, this is the probability that 
 4720  fraction over⊗ow occurs divided by the probability 
 4727  that the operands have the same sign, namely, 
 4735  7%/|→α_↓|f1|d32|)(91%)|4|¬V|415%.|'{A3}|9|1|≡2|≡.|9|4log|β1|
 4736  β0|42.3|4α_↓|4log|β1|β0|42.2|4|¬V|41.930516%.|'
 4737  {A3}|9|1|≡4|≡.|9|4The pages would be uniformly 
 4742  gray (same as ``random point on a slide rule'').|'
 4751  {A3}|9|1|≡5|≡.|9|4The probability that |ε10f|βU|4|¬E|4r 
 4755  |πis |ε(r|4α_↓|41)/10|4α↓|4(r|4α_↓|41)/100|4α+↓|4|¬O|4|¬O|4|
 4756  ¬O|4α=↓|4(r|4α_↓|41)/9. |πSo in this case the 
 4762  leading digits are |εuniformly |πdistributed, 
 4767  e.g., leading digit 1 occurs with probability 
 4774  |f1|d39|).|'{A3}|9|1|≡6|≡.|9|4The probability 
 4777  that there are three leading zero bits is log|β1|β6|42|4α=↓|
 4785  4|f1|d34|); the probability that there are two 
 4792  leading zero bits is log|β1|β6|44|4α_↓|4log|β1|β6|42|4α=↓|4|
 4796  f1|d34|); and similarly for the other two cases. 
 4804  The ``average'' number of leading zero bits is 
 4812  1|f1|d32|), so the ``average'' number of ``signi_cant 
 4819  bits'' is |εp|4α↓|4|f1|d32|). |πThe worst case, 
 4825  |εp|4α_↓|41 |πbits, occurs however with rather 
 4831  high probability. In practice, it is usually 
 4838  necessary to base error estimates on the worst 
 4846  case; in the error analysis of Section 4.2.2, 
 4854  the upper bound on relative rounding error for 
 4862  ⊗oating-hex is 2|ε|g1|gα_↓|gp. |πIn the binary 
 4868  case we can have |εp|4α+↓|41 |πsigni_cant bits 
 4875  at all times (cf. exercise 4.2.1<3), with relative 
 4883  rounding errors bounded by 2|ε|gα_↓|g1|gα_↓|gp. 
 4888  |πExtensive computational experience con_rms 
 4892  that ⊗oating-binary (even with |εp-|πbit precision 
 4898  instead of |εp|4α+↓|41) |πproduce signi_cantly 
 4903  more accurate results than |ε(p|4α+↓|42)-|πbit 
 4908  ⊗oating-hex.|'!!|2Sweeney's tables show that 
 4913  hexadecimal arithmetic can be done a little faster, 
 4921  since fewer cycles are needed when scaling to 
 4929  the right or normalizing to the left. But this 
 4938  fact is insigni_cant compared to the substantial 
 4945  advantages of |εb|4α=↓|42 |πover all other radices 
 4952  (cf. also Theorem 4.2.2C and exercises 4.2.2<15, 
 4959  21), especially since ⊗oating-binary can be made 
 4966  as fast as ⊗oating-hex with only a tiny increase 
 4975  in total processor cost.|'{A3}|π|9|1|≡7|≡.|9|4Suppose 
 4980  that |ε|¬K|βm|4{H11}({H9}F(10|gk|gm|4|¬O|45|gk)|4α_↓|4F(10|g
 4981  k|gm){H11}){H9}|4α=↓|4|πlog|45|ε|gk/|πlog|410|ε|gk 
 4982  |πand |ε|¬K|βm|4{H11}({H9}(F(10|gk|gm|4|¬O|44|gk)|4α_↓|4F(10
 4983  |gk|gm){H11}){H9}|4α=↓|4|πlog|4|ε4|gk/|πlog|4|ε10|gk; 
 4984  |πthen|'{A3}|↔k|uc|)m|)|4{H11}({H9}F(10|gk|gm|4|¬O|45|gk)|4α
 4985  _↓|4F(10|gk|gm|4|¬O|44|gk){H11}){H9}|4α=↓|4|πlog|β1|β0|4|f5|
 4985  d34|)|;{A9}|πfor all |εk. |πBut now let |ε|≤e 
 4993  |πbe a small positive number, and choose |ε|≤d|4|¬Q|40 
 5001  |πso that |εF(x)|4|¬W|4|≤e |πfor 0|4|¬W|4|εx|4|¬W|4|≤d, 
 5006  |πand choose |εM|4|¬Q|40 |πso that |εF(x)|4|¬}Q|*?{A3}|↔k|uc|
 5011  )m|)|4{H11}({H9}F(10|gk|gm|4|¬O|45|gk)|4α_↓|4F(10|gk|gm|4|¬O
 5011  |44|gk){H11}){H9}|4α=↓|4|πlog|β1|β0|4|f5|d34|)|;
 5012  {A9}|πfor all |εk. |πBut now let |ε|≤e |πbe a 
 5021  small positive number, and choose |ε|≤d|4|¬Q|40 
 5027  |πso that |εF(x)|4|¬W|4|≤e |πfor 0|4|¬W|4|εx|4|¬W|4|≤d, 
 5032  |πand choose |εM|4|¬Q|40 |πso that |εF(x)|4|¬Q|41|4α_↓|4|≤e 
 5038  |πfor |εx|4|¬Q|4M. |πWe can take |εk |πso large 
 5046  that 10|ε|gα_↓|gk|4|¬O|45|gk|4|¬W|4|≤d |πand 
 5049  |ε4|gk|4|¬Q|4M; |πhence by the monotonicity of 
 5055  |εF,|'{A3}|↔k|uc|)m|)|4{H11}({H9}F(10|gk|gm|4|¬O|45|gk)|4α_↓
 5056  |4F(10|gk|gm|4|¬O|44|gk){H11}){H9}|4|∂|¬E|4|↔k|uc|)m|¬E0|)|4
 5056  {H11}({H9}F(10|gk|gm|4|¬O|45|gk)|4α_↓|4F(10|gk|g(|gm|gα_↓|g1
 5056  |g)|4|¬O|45|gk){H11}){H9}!|9|;|L!α+↓|4|↔k|uc|)m|¬R0|)|4{H11}
 5057  ({H9}F(10|gk|g(|gm|gα+↓|g1|g)|4|¬O|44|gk)|4α_↓|4F(10|gk|gm|4
 5057  |¬O|44|gk){H11}){H9}>|Lα=↓|4F(10|gα_↓|gk5|gk)|4αt↓|41|4α_↓|4
 5058  F(10|gk4|gk)|4|¬W|42|≤e.>{A3}|9|1|π|≡8|≡.|9|4When 
 5060  |εs|4|¬Q|4r, P|β0(10|gns) |πis 1 for small |εn, 
 5067  |πand 0 when |"l10|ε|gns|"L|4|¬Q|4|"l10|gnr|"L. 
 5071  |πThe least |εn |πfor which this happens may 
 5079  be arbitrarily large, so no uniform bound can 
 5087  be given for |εN|β0(|≤e) |πindependent of |εs. 
 5094  |π(In general, calculus textbooks prove that 
 5100  such a uniform bound would imply that the limit 
 5109  function |εS|β0(s) |πwould be continuous, and 
 5115  it isn't.)|'{A3}|9|1|≡9|≡.|9|4Let |εq|β1, q|β2,|4.|4.|4. 
 5120  |πbe such that |εP|β0(n)|4α=↓|4q|β1(|fnα_↓1|d50|))|4α+↓|4q|β
 5123  2(|fnα_↓1|d51|))|4α+↓|4.|4.|4. |πfor all |εn. 
 5127  |πIt follows that |εP|βm(n)|4α=↓|41|gα_↓|gmq|β1(|fnα_↓1|d50|
 5130  ))|4α+↓|42|gα_↓|gmq|β2(|fnα_↓1|d51|))|4α+↓|4.|4.|4. 
 5131  |πfor all |εn.|'{A3}|π|≡1|≡0|≡.|9|4When |ε1|4|¬W|4r|4|¬W|410
 5135   |πthe generating function |εC(z) |πhas simple 
 5142  poles at the points |ε1|4α+↓|4w|βr, w|βn|4α=↓|42|≤pn|βi/|πln
 5147  |410, |πhence|'{A3}{A6}|εC(z)|4α=↓|4|(|πlog|β1|β0|4|εr|4α_↓|
 5149  41|d21|4α_↓|4z|)|4α+↓|4|↔k|uc|)nn0|)|4|(1|4α+↓|4w|βn|d2w|βn|
 5149  )|4|(e|gα_↓|gw|rn|π|gl|gn|ε|gr|4α_↓|41|d2|π(ln|410)(|εz|4α_↓
 5149  |41|4α_↓|4w|βn)|)|4α+↓|4E(z)|;{A8}|πwhere |εE(z) 
 5152  |πis analytic in the entire plane. Thus if |ε|≤u|4α=↓|4|πarc
 5160  tan(2|ε|≤p/|πln|410),|'{A9}|εc|βm|4|∂α=↓|4|πlog|β1|β0|4|εr|4
 5161  α_↓|41|4α_↓|4|(2|d2|πln|410|)|4|↔k|uc|)|εn|¬Q0|)|4|9|6|↔a|(e
 5161  |urα_↓w|βn|π|1ln|1|εr|)|)|4α_↓|41|d2|εw|βn(1|4α+↓|4w|βn)|gm|
 5161  )|↔s|4α+↓|4e|βm!!!!|;{A4}|Lα=↓|4|πlog|β1|β0|4|εr|4α_↓|41|4α+
 5162  ↓|4|(|πsin(|εm|≤u|4α+↓|42|≤p|4|πlog|β1|β0|4|εr)|4α_↓|4|πsin(
 5162  |εm|≤u)|d2|≤p(1|4α+↓|44|≤p|g2/|π(ln|410)|g2{H11}){H9}|ε|gm|g
 5162  /|g2|)|4α+↓|4O|↔a|(1|d2{H11}({H9}1|4α+↓|416|≤p|g2/|π(ln)|410
 5162  (|g2{H11}){H9}|ε|gm|g/|g2|)|↔s.>{A3}|≡1|≡1|≡.|9|4When 
 5164  (log|ε|βb|4U) |πmod 1 is uniformly distributed 
 5170  in [0,|41), so is (log|ε|βb|41/U)|4|πmod|41|4α=↓|41|4α_↓|4(|
 5174  πlog|ε|βb|4U)|πmod|41. (The latter formula holds 
 5179  except when |εU |πis a power of |εb, |πbut that 
 5189  occurs with probability zero.)|'{A3}|≡1|≡2|≡.|9|4|εh(z)|4α=↓
 5193  |4|¬J|urz|)1/b|)|4f(x)|4dxg(z/bx)/bx|4α+↓|4|¬J|ur1|)z|)|4f(x
 5193  )|4dxg(z/x)/x, |πand |εl(z)|4α=↓|4|¬J|urz|)1/b|)|4f(x)|4dxl(
 5195  z/bx)/bx|4α+↓|4|¬J|ur1|)z|)|4f(x)|4dxl(z/x)/x, 
 5196  |πhence |ε{H11}({H9}h(z)|4α_↓|4l(z){H11}){H9}/l(z)|4α=↓|4|¬J
 5197  |urz|)1/b|)|4f(x)|4dx{H11}({H9}g(z/bx)|4α_↓|4l(z/bx){H11}){H
 5197  9}/l(z/bx)|4α+↓|4|¬J|ur1|)z|)|4f(x)|4dx{H11}({H9}g(z/x)|4α_↓
 5197  |4l(z/x){H11}){H9}/l(z/x). |πSince |εf(x)|4|¬R|40, 
 5200  |¬G{H11}({H9}h)z)|4α_↓|4l(z){H11})/l(z)|¬G|4|¬E|4|¬J|urz|)1/
 5200  b|)|4f(x)|4dxA(g)|4α+↓|4|¬J|ur1|)z|)|4f(x)|4dxA(g) 
 5201  |πfor all |εz, |πhence |εA(h)|4|¬E|4A(g). |πBy 
 5207  symmetry, |εA(h)|4|¬E|4A(f). |π[|εBell System 
 5211  Tech. J. |≡4|≡9 (1970), 1609<1625.]|'{A3}|π|≡1|≡3|≡.|9|4Let 
 5217  |εX|4α=↓|4|π(log|ε|βb|4U)|πmod|41, |εY|4α=↓|4|π(log|ε|βb|4V)
 5218  |πmod 1, so that |εS |πand |εY |πare independently 
 5227  and uniformly distributed in [0,|41). No left 
 5234  shift is needed if and only if |εX|4α+↓|4Y|4|¬R|41, 
 5242  |πand this occurs with probability |f1|d32|).|'
 5248  !!|2(Similarly, this needs only the weaker assumption 
 5255  that both operands independently have the |εsame 
 5262  |πdistribution.)|'{A3}|≡1|≡4|≡.|9|4For convenience, 
 5265  the calculations are shown here for |εb|4α=↓|410. 
 5272  |πIf |εk|4α=↓|40, |πthe probability of a carry 
 5279  is|'{A9}|↔a|ε|(1|d2|πln|410|)|↔s|g2|↔j|uc|)|ε1|¬Ex,y|¬E10|dx
 5280  α+↓y|¬R10|)|4|(dx|d2x|)|4|(dy|d2y|)|1|1.|;{A9}|π(See 
 5282  Fig. A-7.) The value of the integral is|'{A9}|ε|↔j|ur10|)0|)
 5290  |4|(dy|d2y|)|4|↔j|ur10|)10α_↓y|)|4|(dx|d2x|)|4α_↓|42|↔j|ur1|
 5290  )0|)|4|(dy|d2y|)|↔j|ur10|)10α_↓y|)|(dx|d2x|)|1|1,|;
 5291  |πand|'{A9}|ε|↔j|urt|)0|)|(dy|d2y|)|4|πln|↔a|(1|d21|4α_↓|4|ε
 5292  y/10|)|↔s|4α=↓|4|↔j|urt|)0|)|↔a|(1|d210|)|4α+↓|4|(y|d2200|)|
 5292  4α+↓|4|(y|g2|d23000|)|4α+↓|4|¬O|4|¬0|4|¬0|↔s|4dy|4α=↓|4|(t|d
 5292  210|)|4α+↓|4|(t|g2|d2400|)|4α+↓|4|(t|g3|d29000|)|4α+↓|4|¬O|4
 5292  |¬O|4|¬O|4.|;|π(The latter integral is essentially 
 5298  a ``dilogarithm'' integral.) Hence the probability 
 5304  of a carry when |εk|4α=↓|40 |πis (1/ln|410)|g2(|ε|≤p|g2/6|4α
 5310  _↓|42|4|¬K|βn|β|¬R|β1|41/n|g210|gn)|4α=↓|4.27154. 
 5311  [Note|*/:|\ |πWhenn |*?*?*?εb|4α=↓|42 |πand |εk|4α=↓|40, 
 5316  |πfraction over⊗ow |εalways |πoccurs, so this 
 5322  derivation proves that |ε|¬K|βn|β|¬R|β1|41/n|g22|gn|4α=↓|4|≤
 5325  p|g2/12|4α_↓|4|f1|d32|)(|πln|42)|g2.]|'!!|2When 
 5327  |εk|4|¬Q|40, |πthe probability is|'{A8}|↔a|(1|d2ln|410|)|↔s|
 5331  g2|↔j|ur|ε10|g1|gα_↓|gk|)10|gα_↓|gk|)|1|1|(dy|d2y|)|↔j|ur10|
 5331  )10α_↓y|)|(dx|d2x|)|4α=↓|4|↔a|(1|d2|πln|410|)|↔s|g2|↔a|↔k|uc
 5331  |)n|¬R1|)|4|(1|d2|εn|g210|gn|gk|)|4α_↓|4|↔k|uc|)n|¬R1|)|4|(1
 5331  |d2n|g210|gn|g(|gk|gα+↓|g1|g)|)|↔s.|;{A9}|πThus 
 5333  when |εb|4α=↓|410, |πfraction over⊗ow should 
 5338  occur with probability .272|εp|β0|4α+↓|4.017p|β1|4α+↓|4.002p
 5341  |β2|4α+↓|4|¬O|4|¬O|4|¬O|4. |πWhen |εb|4α=↓|42 
 5344  |πthe corresponding _gures are |εp|β0|4α+↓|4.655p|β1|4α+↓|4.
 5348  288p|β2|4α+↓|4↓137p|β3|4α+↓|4.067p|β4|4α+↓|4|¬O|4|¬O|4|¬O|4.
 5348  |'!!|2|πNow if we use the probabilities from 
 5356  Sweeney's _rst table, dividing by .92 to eliminate 
 5364  zero operands, and assuming that the probabilities 
 5371  are independent of the operand signs, we predict 
 5379  a probability of about 14 percent when |εb|4α=↓|410, 
 5387  |πinstead of the 15 percent in exercise 1. For 
 5396  |εb|4α=↓|42, |πwe predict about 48 percent, while 
 5403  the table yeilds 44 percent. These results are 
 5411  certainly in agreement within the limits of experimental 
 5419  error.|'{A3}|≡1|≡5|≡.|9|4When |εk|4α=↓|40, |πthe 
 5423  leading digit is 1 if and only if there is a 
 5434  carry. (It is possible for fraction over⊗ow and 
 5442  subsequent rounding to yield a leading digit 
 5449  of 2, when |εb|4|¬R|44, |πbut we are ignoring 
 5457  rounding in this exercise.) The probability of 
 5464  fraction over⊗ow is .272|4|¬W|4log|β1|β0|42, 
 5468  as shown in the previous exercise.|'!!|2When 
 5475  |εk|4|¬Q|40, |πthe leading digit is 1 with probability|'
 5483  {A9}|↔a|(1|d2ln|410|)|↔s|g2|↔a|↔j|ur10|ε|g1|gα_↓|gk|)10|gα_↓
 5483  |gk|)|1|1|(dy|d2y|)|↔j|ur|)1|¬Ex|¬W2α_↓y!!!|5|)|(dx|d2x|)|↔s
 5483  |4|¬W|4|↔a|(1|d2|πln|410|)|↔s|g2|↔a|ε|↔j|ur10|g1|gα_↓|gk|)10
 5483  |gα_↓|gk|)|(dy|d2y|)|↔j|ur|)1|¬Ex|¬E2|(dx|d2x|)|↔s|4α=↓|4|πl
 5483  og|β1|β0|42.|;{A3}|≡1|≡6|≡.|9|4To prove the hint 
 5488  [qhich is due to Landu, |εPrace matematyczno-⊂zyczne 
 5495  |≡2|≡1 (1910), 103<113], |πassume _rst that lim|4sup|4|εa|βn
 5501  |4α=↓|4|↔l|4|¬Q|40. |πLet |ε|≤e|4α=↓|4|≤l/(|≤l|4α+↓|44M) 
 5504  |πand choose |εN |πso that |ε|¬Ga|β1|4α+↓|4|¬O|4|¬O|4|¬O|4α+
 5509  ↓|4a|βn|¬G|4|¬W|4|f1|d310|)|≤e|≤ln |πfor all 
 5512  |εn|4|¬Q|4N. |πLet |εn|4|¬Q|4N/(1|4α_↓|4|≤e), 
 5515  n|4|¬Q|45/|≤e |πbe such that |εa|βn|4|¬Q|4|f1|d32|)|≤l. 
 5520  |πThen by induction |εa|βn|βα_↓|βk|4|¬R|4a|βn|4α_↓|4kM/(n|4α
 5523  _↓|4|≤en)|4|¬Q|4|f1|d34|)|≤l |πfor |ε0|4|¬E|4k|4|¬W|4|≤en, 
 5526  |πand |ε|¬K|ur|)nα_↓|≤en|¬Wk|¬En|)|4a|βk|4|¬R|4|f1|d34|)|≤l(
 5527  |≤en|4α_↓|41)|4|¬Q|4|f1|d35|)|≤l|≤en. |πBut |ε|¬G|¬K|ur|)nα_
 5529  ↓|≤en|¬Wk|¬En|4a|βk|¬G|4α=↓|4|¬G|¬K|ur|)1|¬Ek|¬En|)|4a|βk|4α
 5529  _↓|4|¬K|ur|)1|¬Ek|¬Enα_↓|≤en|)|4a|βk|¬G|4|¬E|4|f1|d35|)|≤e|≤
 5529  ln |πsince |εn|4α_↓|4|≤en|4|¬Q|4N. |πA similar 
 5534  contradiction applies if lim|4ing|4|εa|βn|4|¬W|40.|'
 5538  |π!!|2Assuming that |εP|βm|βα+↓|β1(n)|4|¬M|4|≤l 
 5541  |πas |εn|4|¬M|4|¬X, |πlet |εa|βk|4α=↓|4P|βm(k)|4α_↓|4|≤l. 
 5545  |πIf |εm|4|¬Q|40, |πthe |εa|βk |πsatisfy the 
 5551  hypotheses of the hint (cf. Eq. 4.2.2<15), |εm|4|¬Q|40, 
 5559  |πthe |εa|βk |πsatisfy the hypotheses of the 
 5566  hint (cf. Eq. 4.2.2<15), |πsince |ε0|4|¬E|4P|βm(k)|4|¬E|41; 
 5572  |πhence |εP|βm(n)|4|¬M|4|≤l.|'{A3}|π|≡1|≡7|≡.|9|4See 
 5575  |εFibonacci Quarterly |≡7 (1969), 474<475. |π(Persi 
 5581  Diaconis [Ph.D. thesis, Harvard University, 1974] 
 5587  has shown among other things that the de_nition 
 5595  of probability by repeated averaging is weaker 
 5602  than harmonic probability, in the following precise 
 5609  sense: If lim|ε|βm|β|¬M|β|¬X|4|πlim|4inf|ε|βn|β|¬M|β|¬X|4Pm(
 5611  n)|4α=↓|4|πlim|ε|βm|β|¬M|β|¬X|4|πlim|4sup|ε|βn|β|¬M|β|¬X|4P|
 5611  βn(n)|4α=↓|4|≤l |πthen the harmonic probability 
 5616  is |ε|≤l. |πOn the other hand the statement ``10|ε|gk|i2|4|¬
 5624  E|4n|4|¬W|410|gk|i2|gα+↓|gk |πfor some integer 
 5628  |εk|4|¬Q|40'' |πhas logarithmic probability |f1|d32|), 
 5633  while repeated averaging never settles down to 
 5640  give it any particular probability.)|'|Hβ{U0}{H9L11M29}|π583
folio 754 galley 6
 5645  20#Computer Programming!(Knuth/Addison-Wesley)!f. 
 5647  754!Ans!g. 6|'{A25}{H10L12}|∨S|∨E|∨C|∨T|∨I|∨O|∨N|9|∨4|∨.|∨3|
 5649  ∨.|∨1|'{A11}{H9L11}|9|1|≡2|≡.|9|4If the |εi|πth 
 5653  number to be added is |εu|βi|4α=↓|4(u|βi|β1u|βi|β2|4.|4.|4.|
 5658  4u|βi|βn)|βb, |πuse Algorithm A with step A2 
 5665  changed to the following:|'{I3.4H}!!|2|≡A|≡2|¬S|≡.|9[Add 
 5670  digits.] Set |εw|βj|4|¬L|4(u|β1|βj|4α+↓|4|¬O|4|¬O|4|¬O|4α+↓|
 5672  4u|βm|βj|4α+↓|4k)|πmod|4|εb, |πand |εk|4|¬L|4|"l(u|β1|βj|4α+
 5674  ↓|4|¬O|4|¬O|4|¬O|4α+↓|4u|βm|βj|4α+↓|4k)/b|"L. 
 5675  |π[The maximum value of |εk |πis |εm|4α_↓|41, 
 5682  |πso step A3 would have to be altered if |εm|4|¬Q|4b.)|'
 5692  {A3}{IC}|π|h|∂|9|1|≡3|≡.|9|4|∂|¬2|¬h!|∂|¬e|¬n|¬t|¬2!|∂|¬mα/↓
 5692  |¬n|≤*/|¬n|¬,|¬1!!|∂|εMN!!|∂|π(loc itititi|E|n|'
 5694  |L|9|1|≡3|≡.|L|L|¬e|¬n|¬t|¬1|L|¬n|L|91>|L|L|L|¬j|¬o|¬v|L|¬o|
 5695  ¬f|¬l|¬o|L|91|LEnsure over⊗ow is o=.>|L|L|L|¬e|¬n|¬t|¬a|L|¬0
 5699  |L|91|L|εk|4|¬L|40.>|L|L|π|¬2|¬h|L|¬e|¬n|¬t|¬2|L|¬0|L|4|4|εN
 5700  |L|π(rI2|4|"o|4next value of |εk)>|L|L|L|π|¬e|¬n|¬t|¬3|L|¬mα
 5704  /↓|¬n|≤*/|¬n|¬,|¬1|L|4|4|εN|L|π{H11}({H9}|¬l|¬o|¬c|ε(u|βi|βj)
 5704  |4|"o|4|¬u|4α+↓|4n(i|4α_↓|41)|4α+↓|4j{H11}){H9}>
 5705  |L|L|π|¬3|¬h|L|¬a|¬d|¬d|L|¬u|¬,|¬3|L|εMN|L|πrA|4|¬L|4rA|4α+↓
 5705  |4|εu|βi|βj.|π>|L|L|L|¬j|¬n|¬o|¬v|Lα/↓|≤%|¬2|L|εMN|L>
 5707  |π|L|L|L|¬i|¬n|¬c|¬2|¬1|L|ε|6K|L|πCarry one.>
 5709  |L|L|L|¬d|¬e|¬c|¬3|L|¬n|L|εMN|L|πRepeat for |εb|4|¬R|4i|4|¬R
 5711  |40.|π>|L|L|L|¬j|¬3|¬p|L|¬3|¬b|L|εMN|L|π{H11}({H9}rI3|4|"o|4
 5712  |εn(i|4α_↓|41)|4α+↓|4j{H11}){H9}|π>|L|L|L|¬s|¬t|¬a|L|¬w|¬,|¬
 5713  1|L|4|4|εN|Lw|βj|4|¬L|4|πrA.>|L|L|L|¬e|¬n|¬t|¬a|L|¬0|¬,|¬2|L
 5714  |4|4|εN|Lk|4|¬L|4|πrI2.>|L|L|L|¬d|¬e|¬c|¬1|L|¬1|L|4|4|εN|π>
 5716  |L|L|L|¬j|¬i|¬p|L|¬2|¬b|L|4|4|εN|L|πRepeat for 
 5718  |εn|4|¬R|4j|4|¬R|40.>|L|L|L|π|¬s|¬t|¬a|L|¬w|L|91|LStore 
 5720  _nal carry in |εw|β0.>{A9}|πRunning time, assuming 
 5727  that |εK|4α=↓|4|f1|d32|)MN, |πis 5.5|εMN|4α+↓|47N|4α+↓|44 
 5731  |πcycles.|'{A3}|π|9|1|≡4|≡.|9|4We may make the 
 5736  following assertion before A1: |ε``n|4|¬R|41; 
 5741  |πand 0|4|¬E|4|εu|βi, v|βi|4|¬W|4b |πfor |ε1|4|¬E|4i|4|¬E|4n
 5745  .'' |πBefore A2, we assert: ``1|4|¬E|4|εj|4|¬E|4n; 
 5751  0|4|¬E|4u|βi, v|βi|4|¬W|4b |πfor 1|4|¬E|4|εi|4|¬E|4n; 
 5755  0|4|¬E|4w|βi|4|¬W|4b |πfor |εj|4|¬W|4i|4|¬E|4n; 
 5758  |π0|4|¬E|4|εk|4|¬E|41; |πand|'{A9}|ε(u|βj|βα+↓|β1|4.|4.|4.|4
 5760  u|βn)|βb|4α+↓|4(v|βj|βα+↓|β1|4.|4.|4.|4v|βn)|βb|4α=↓|4(kw|βj
 5760  |βα+↓|β1|4.|4.|4.|4w|βn)|βb.''|;{A9}|πThe latter 
 5763  statement means more precisely that|'{A3}|ε|↔k|uc|)j|¬Wt|¬En
 5768  |)|4u|βtb|gn|gα_↓|gt|4α+↓|4|↔k|uc|)j|¬Wt|¬En|)|4v|βtb|gn|gα_
 5768  ↓|gt|4α=↓|4kb|gn|gα_↓|gj|4α+↓|4|↔k|uc|)j|¬Wt|¬En|)|4w|βtb|gn
 5768  |gα_↓|gt.|;{A9}*?*?*?*?|πBefore A3, we assert: ``1|4|¬E|4|εj|4|¬
 5773  E|4n; 0|4|¬E|4u|βi, v|βi|4|¬W|4b |πfor 1|4|¬E|4|εi|4|¬E|4n; 
 5778  0|4|¬E|4w|βi|4|¬W|4b |πfor |εj|4|¬E|4i|4|¬E|4n; 
 5781  0|4|¬E|4k|4|¬E|41; |πand |ε(u|βj|4.|4.|4.|4u|βn)|βb|4α+↓|4(v
 5783  |βj|4.|4.|4.|4v|βn)|βb|4α=↓|4(kw|βj|4.|4.|4.|4w|βn)|βb.'' 
 5784  |πAfter A3, we assert that 0|4|¬E|4|εw|βi|4|¬W|4b 
 5790  |πfor 1|4|ε|¬E|4i|4|¬E|4n; 0|4|¬E|4w|β0|4|¬E|41; 
 5793  |πand |ε(u|β1|4.|4.|4.|4u|βn)|βb|4α+↓|4(v|β1|4.|4.|4.|4v|βn)
 5794  |βb|4α=↓|4(w|β0|4.|4.|4.|4w|βn)|βb.|'!!|2|πIt 
 5796  is a simple matter to complete the proof by verifying 
 5806  the necessary implications between the assertions 
 5812  and by showing that the algorithm always terminates.|'
 5820  {A3}{I3.1H}|9|1|≡5|≡.|9|4|≡B|≡1|≡.|9Set |εj|4|¬L|41, 
 5822  w|β0|4|¬L|40.|'!!|2|π|≡B|≡2|≡.|9Set |εt|4|¬L|4u|βj|4α+↓|4v|β
 5824  j, w|βj|4|¬L|4t|4|πmod|4|εb, i|4|¬L|4j.|'!!|2|π|≡B|≡3|≡.|9If
 5827   |εt|4|¬R|4b, |πset |εi|4|¬L|4i|4α_↓|41, t|4|¬L|4w|βi|4α+↓|4
 5831  1, w|βi|4|¬L|4t|4|πmod|4|εb, |πand repeat this 
 5836  step until |εt|4|¬L|4b.|'!!|2|π|≡B|≡.|9Increase 
 5840  |εj |πby one, and if |εj|4|¬E|4n |πgo back to 
 5849  B2.|'{A3}|9|1|≡6|≡.|9|4|2|≡C|≡1|≡.|9Set |εj|4|¬L|41, 
 5852  i|4|¬L|40, r|4|¬L|40.|'!!|4|π|≡C|≡2|≡.|9|4Set 
 5855  |εt|4|¬L|4u|βj|4α+↓|4v|βj. |πIf |εt|4|¬R|4b, 
 5858  |πset |εw|βi|4|¬L|4r|4α+↓|41, w|βk|4|¬L|40 |πfor 
 5862  |εi|4|¬W|4k|4|¬W|4j, |πset |εi|4|¬L|4j, |πand 
 5866  |εr|4|¬L|4t|4|πmod|4|εb. |πOterwise if |εt|4|¬W|4b|4α_↓|41, 
 5870  |πset |εw|βi|4|¬L|4r, w|βk|4|¬L|4b|4α_↓|41 |πfor 
 5874  |εi|4|¬W|4k|4|¬W|4j, |πset |εi|4|¬L|4j, |πand 
 5878  |εr|4|¬L|4t.|'!!|4|π|≡C|≡3|≡.|9Increase |εj |πby 
 5882  one. If |εj|4|¬E|4n, |πgo back to C2; otherwise 
 5890  set |εw|βi|4|¬L|4r, |πand |εw|βk|4|¬L|4b|4α_↓|41 
 5894  |πfor |εi|4|¬W|4k|4|¬E|4n.|'{A3}{IC}|π|9|1|≡7|≡.|9|4When 
 5897  |εj|4α=↓|43, |πfor example, we hjave |εk|4α=↓|40 
 5903  |πwith probability |ε(b|4α+↓|41)/2b, k|4α=↓|41 
 5907  |πwith probability |ε{H11}({H9}(b|4α_↓|41)/2b{H11}){H9}(1|4α
 5909  _↓|41/b), |πnamely the probability that a carry 
 5916  occurs and thathe preceding digit wasn't |εb|4α_↓|41; 
 5923  k|4α=↓|42 |πwith probability {H11}({H9}(|εb|4α_↓|41)/2b{H11}
 5926  ){H9}(1|4α_↓|41/b); |πand |εk|4α=↓|43 |πwith 
 5930  probability {H11}({H9}(|εb|4α_↓|41)/2b{H11}){H9}(1/b)(1/b)(1
 5931  ). |πFor _xed |εk |πwe may add the probabilities 
 5940  as |εj |πvaries from 1 to |εn; |πthis gives the 
 5950  mean number of times the carry propagates back 
 5958  |εk |πplaces,|'{A9}|εm|βk|4α=↓|4|(b|4α_↓|41|d22b|gk|){H11}|↔
 5960  a{H9}(n|4α+↓|41|4α_↓|4k)|↔a1|4α_↓|4|(1|d2b|)|↔s|4α+↓|4|(1|d2
 5960  b|){H11}|↔s{H9}.|;{A9}|πAs a check, we _nd that 
 5967  the average number of carries is|'{A9}|εm|β1|4α+↓|42m|β2|4α+
 5973  ↓|4|¬O|4|¬O|4|¬O|4α+↓|4nm|βn|4α=↓|4|(1|d22|){H11}|↔a{H9}n|4α
 5973  _↓|4|(1|d2b|4α_↓|41|)|↔a1|4α_↓|4|↔a|(1|d2b|)|↔s|gn|↔s{H11}|↔
 5973  s{H9},|;{A9}|πin agreement with (6).|'{A3}|π|h|9|1|∂|≡8|≡.|9
 5978  |4|∂|¬1|¬h!|∂|¬e|¬n|¬n|¬i!|∂|¬u|≤%|¬n|≤%|¬1|¬,|¬1!!|∂|εN!!!!
 5978  |∂|¬2|¬h!|π|∂|¬i|¬n|¬c|¬a!|∂|¬w|≤%|¬n|≤%|¬1|¬,|¬2!!|∂|εK|E|n
 5978  |;|π|L|≡8|≡.|L|¬e|¬n|¬n|¬i|L|¬n|L1|L|¬2|¬h|L|¬l|¬d|¬a|L|¬w|≤
 5979  %|¬n|≤%|¬1|¬,|¬2|L|εK>|π|L|L|L|¬j|¬o|¬v|L|¬o|¬f|¬l|¬o|L1|L|L
 5980  |¬i|¬n|¬c|¬a|L|¬1|L|εK>|L|L|L|¬s|¬t|¬z|π|L|¬w|L1|L|L|¬s|¬t|¬
 5981  a|L|¬w|≤%|¬n|≤%|¬1|¬,|¬2|L|εK|π>|L|L|¬1|¬h|L|¬l|¬d|¬a|L|¬u|≤
 5982  %|¬n|≤%|¬1|¬,|¬1|L|εN|L|L|π|¬d|¬e|¬c|¬2|L|¬1|L|εK>
 5983  |π|L|L|L|¬a|¬d|¬d|L|¬v|≤%|¬n|≤%|¬1|¬,|¬1|L|εN|L|L|π|¬j|¬o|¬v
 5983  |L|¬2|¬b|ε|LK|π>|L|L|L|¬s|¬t|¬a|L|¬w|≤%|¬n|≤%|¬1|¬,|¬1|ε|LN|
 5984  π|L|¬3|¬h|L|¬i|¬n|¬c|¬2|L|¬1|ε|LN>|π|L|L|L|¬j|¬n|¬o|¬v|L|¬3|
 5985  ¬f|ε|LN|π|L|¬3|¬h|L|¬i|¬n|¬c|¬2|L|¬1|ε|LN>|π|L|L|L|¬e|¬n|¬t|
 5986  ¬2|L|≤*/|¬1|¬,|¬1|ε|LL>{A9}|πThe running time 
 5990  depends on |εL, |πthe number of positions in 
 5998  which |εu|βj|4α↓|4v|βj|4|¬R|4b; |πand on |εK, 
 6003  |πthe total number of carries. It is not di∃cult 
 6012  to see that |εK |πis the same quantity analysis 
 6021  in the text shows that |εL |πhas the average 
 6030  value |εN{H11}({H9}(b|4α_↓|41)/2b{H11}){H9}, 
 6032  |πand |εK |πhas the average value |f1|d32|)(|εN|4α_↓|4b|gα_↓
 6038  |g1|4α_↓|4b|gα_↓|g2|4α_↓|4|¬O|4|¬O|4|¬O|4α_↓|4b|gα_↓|gn). 
 6039  |πSo if we ignore terms of order 1/|εb, |πthe 
 6048  running time is |ε9N|4α↓|4L|4α+↓|47K|4α+↓|43|4|¬V|413N|4α+↓|
 6051  43 |πcycles.|'!!|2|εNote|*/:|\ |πSince a carry 
 6057  occurs almost half of the time, it would be more 
 6067  e∃cient to delay storing the result by one step. 
 6076  This leads to a somewhat longer program whose 
 6084  running time is approximately 12|εN|4α+↓|455 
 6089  *?*?!!|2|εNote|*/:|\ |πSince a carry occurs almost 
 6095  half of the time, it would be more e∃cient to 
 6105  delay storing the result by one step. This leads 
 6114  to a somewhat longer program whose running time 
 6122  is approximately 12|εN|4α+↓|45 |πcycles, based 
 6127  on the somewhat more detailed information calculated 
 6134  in exercise 7.|'{A3}|9|1|≡9|≡.|9|4Replace |ε``b'' 
 6139  |πby |ε``b|βn|βα_↓|βj'' |πeverywhere in step 
 6144  A2.|'{A3}|≡1|≡0|≡.|9|4If lines 06 and 07 were 
 6151  interchanged, we would almost always have over⊗ow, 
 6158  but register A might have a negative value at 
 6167  line 08, so this would not work. If the instructions 
 6177  on lines 05 and 06 were interchanged, the sequence 
 6186  of over⊗ows occurring in the program would be 
 6194  slightly di=erent in some cases, but the program 
 6202  would still be right.|'{A3}|≡1|≡1|≡.|9|4(a) Set 
 6208  |εj|4|¬L|41; |π(b) if |εu||≡1|≡1|≡.|9|4(a) Set 
 6213  |εj|4|¬L|41; |π(b) if |εu|βj|4|¬W|4v|βj, |πterminate 
 6218  |ε[u|4|¬W|4v]; |πif |εu|βj|4α=↓|4v|βj |πand |εj|4α=↓|4n, 
 6223  |πterminate |ε[u|4α=↓|4v]; |πif |εu|βj|4α=↓|4v|βj 
 6227  |πand |εj|4|¬W|4n, |πset |εj|4|¬L|4j|4αt↓|41 
 6231  |πand repeat (b); if |εu|βj|4|¬Q|4v|βj, |πterminate 
 6237  |ε[u|4|¬Q|4v]. |πThis algorithm tends to be quite 
 6244  fast, since there is usually low probability 
 6251  that |εj |πwill have to get very high before 
 6260  we encounter a case with |εu|βj|4|=|↔6α=↓|4v|βj.|'
 6266  {A3}|π|≡1|≡2|≡.|9|4Use Algorithm S with |εu|βj|4α=↓|40 
 6271  |πand |εv|βj|4α=↓|4w|βj. |πAnother ``borrow'' 
 6275  will occur at the end of the algorithm, which 
 6284  this time should be ignored.|'{A3}|≡1|≡3|≡.|9|4|∂!|6!|∂|¬e|¬
 6289  n|¬t|¬x!|∂|¬n!!|4|4|4!!|∂1|'|L|L|¬j|¬o|¬v|L|¬o|¬f|¬l|¬o|L1>
 6291  |L|L|¬e|¬n|¬t|¬x|L|¬o|L1>|L|¬2|¬h|L|¬s|¬t|¬x|L|¬c|¬a|¬r|¬r|¬
 6292  y|L|εN|π>|L|L|¬l|¬d|¬a|L|¬u|¬,|¬1|ε|LN|π>|L|L|¬m|¬u|¬l|L|¬v|
 6294  L|εN|π>|L|L|¬s|¬l|¬c|L|¬5|εN|π>|L|L|¬a|¬d|¬d|L|¬c|¬a|¬r|¬r|¬
 6296  y|ε|LN|π>|L|L|¬j|¬n|¬o|¬v|Lα/↓|≤%|¬2|ε|LN|π>|L|L|¬ki*?*?*?*?x|L|
 6298  ¬1|ε|LK|π>|L|L|¬s|¬t|¬a|L|¬w|¬,|¬1|ε|LN>|π|L|L|¬d|¬e|¬c|¬1|L
 6300  |¬1|ε|LN|π>|L|L|¬j|¬1|¬p|L|¬2|¬b|ε|LN|π>|L|L|¬s|¬t|¬x|L|¬w|L
 6302  1>{A9}The running time is 23|εN|4α↓|4K|4α+↓|45 
 6308  |πcycles, and |εK |πis roughly |ε|f1|d32|)N.|'
 6314  {A3}|π|≡1|≡4|≡.|9|4The key inductive assertion 
 6318  is the one which should be valid at the beginning 
 6328  of step M4; all others are readily _lled in from 
 6338  this one, which is as follows: ``1|4|¬E|4|εi|4|¬E|4n; 
 6345  1|4|¬E|4j|4|¬E|4m; 0|4|¬E|4u|βr|4|¬W|4b |πfor 
 6348  |ε1|4|¬E|4r|4|¬E|4n; 0|4|¬E|4v|βr|4|¬W|4b |πfor 
 6351  |ε1|4|¬E|4r|4|¬E|4m; 0|4|¬E|4w|βr|4|¬W|4b |πfor 
 6354  |εj|4|¬W|4r|4|¬E|4m|4α+↓|4n; 0|4|¬E|4k|4|¬W|4b; 
 6356  |πand|'{A9}|ε(w|βj|βα↓|β1|4.|4.|4.|4w|βm|βα+↓|βn)|βb|4α+↓|4k
 6357  b|gm|gα+↓|gn|gα_↓|gi|gα_↓|gj|4α=↓|4u|4α⊗↓|4(v|βj|βα+↓|β1|4.|
 6357  4.|4.|4v|βm)|βb|4α+↓|4(u|βi|βα+↓|β1|4.|4.|4.|4u|βn)|βb|4α⊗↓|
 6357  4v|βjb|gm|gα_↓|gj*2.*?*?*?*?{A9}|ε(w|βj|βα↓|β1|4.|4.|4.|4w|βm|βα+
 6357  ↓|βn)|βb|4α+↓|4kb|gm|gα+↓|gn|gα_↓|gi|gα_↓|gj|4α=↓|4u|4α⊗↓|4(
 6357  v|βj|βα+↓|β1|4.|4.|4.|4v|βm)|βb|4α+↓|4(u|βi|βα+↓|β1|4.|4.|4.
 6357  |4u|βn)|βb|4α⊗↓|4v|βjb|gm|gα_↓|gj.''|;{A9}|π(For 
 6359  the precise meaning of this notation, see the 
 6367  answer to exercise 4.)|'{A3}|≡1|≡5|≡.|9|4The 
 6372  error is nonnegative and less than |ε(n|4α_↓|42)b|gα_↓|gn|gα
 6378  _↓|g1. |π{H11}({H9}Similarly, if we ignore the 
 6384  products with |εi|4α+↓|4j|4|¬Q|4n|4α+↓|43, |πthe 
 6388  error is bounded by |ε(b|4α_↓|43)b|gα_↓|gn|gα_↓|g2, 
 6393  |πetc.; but, in qome cases, we must compute all 
 6402  of the products if we want to get the true rounded 
 6413  result.{H11}){H9}|'{A3}|≡1|≡6|≡.|9|4|≡S|≡1|≡.|9Set 
 6415  |εr|4|¬L|40, j|4|¬L|41.|'!!|2|π|≡S|≡2|≡.|9Set 
 6418  |εw|βj|4|¬L|4|"l(rb|4α+↓|4u|βj)/v|"L, r|4|¬L|4(rb|4α+↓|4u|βj
 6419  )|πmod|4|εv.|'!!|2|π|≡S|≡3|≡.|9Increase |εj |πby 
 6423  1, and return to S2 if |εj|4|¬E|4n.|'{A3}|π|≡1|≡7|≡.|9|4|εu/
 6430  v|4|¬Q|4u|β0b|gn/(v|β1|4α+↓|41)b|gn|gα_↓|g1|4α=↓|4b({H11}({H
 6430  9}1|4α_↓|41/(v|β1|4αt↓|41){H11}){H9}|4|¬Q|4b{H11}({H9}1|4α_↓
 6430  |41/(b/2){H11}){H9}|4α=↓|4b|4α_↓|42.|'{A3}|π|≡1|≡8|≡.|9|4|ε(
 6431  u|β0b|4α+↓|4u|β1)/(v|β1|4α+↓|41)|4|¬E|4u/(v|β1|4α+↓|41)b|gn|
 6431  gα_↓|g1|4|¬W|4u/v.|'{A3}|π|≡1|≡9|≡.|9|4|εu|4α_↓|4|=7qv|4|¬E|
 6432  4u|4α_↓|4|=7qv|β1b|gn|gα_↓|g1|4α_↓|4|=7qv|β2b|gn|gα_↓|g2|4α=
 6432  ↓|4u|β2b|gn|gα_↓|g2|4α+↓|4|¬O|4|¬O|4|¬O|4α+↓|4u|βn|4α+↓|44*?*?
 6432  |gn|gα≠↓*4g1|4α_↓|4|=7qv|β2b|gn|gα_↓|g2|4|¬W|4b|gn|gα_↓|g2(u|
 6432  β2|4α+↓|41|4α+↓|4|=7rb|4α_↓|4|=7qv|β2)|4|¬E|40. 
 6433  |πSince |εu|4α_↓|4|=7qv|4|¬W|40, q|4|¬W|4|=7q.|'
 6436  {A3}|π|≡2|≡0|≡.|9|4If |εq|4|¬E|4|=7q|4α_↓|42, 
 6438  |πthen |εu|4|¬W|4(|=7q|4α_↓|41)v|4|¬W|4|=7q(v|β1b|gn|gα_↓|g1
 6439  |4α+↓|4(v|β2|4α+↓|41)b|gn|gα_↓|g2{H11}){H9}|4α_↓|4v|4|¬W|4|=
 6439  7qv|β1b|gn|gα_↓|g1|4α+↓|4|=7qv|β2b|gn|gα_↓|g2|4α+↓|4b|gn|gα_
 6439  ↓|g1|4α_↓|4v|4|¬E|4|=7qv|β1b|gn|gα_↓|g1|4α+↓|4(b|=7r|4α+↓|4u
 6439  |β2)b|gn|gα_↓|g2|4α+↓|4b|gn|gα_↓|g1|4α_↓|4v|4α=↓|4u|β0b|gn|4
 6439  α+↓|4u|β1b|gn|gα_↓|g1|4α+↓|4u|β2b|gn|gα_↓|g2|4α+↓|4b|gn|gα_↓
 6439  |g1|4α_↓|4v|4|¬E|4u|β0b|gn|4α+↓|4u|β1b|gn|gα_↓|g1|4α+↓|4u|β2
 6439  b|gn|gα_↓|g2|4|¬E|4u. |πIn other words, |εu|4|¬W|4u, 
 6444  |πand this is a contradiction.|'{A3}|≡2|≡1|≡.|9|4Assume 
 6450  that |εu|4α_↓|4qv|4|¬W|4(1|4α_↓|43/b)v; |πthen 
 6453  |ε|=7q(v|4α_↓|4b|gn|gα_↓|g2)|4|¬W|4|=7q(v|β1b|gn|gα_↓|g1|4α+
 6453  ↓|4v|β2b|gn|gα_↓|g2)|4|¬E|4u|β0b|gn|4α+↓|4u|β1b|gn|gα_↓|g1|4
 6453  α+↓|4u|β2b|gn|gα_↓|g2|4|¬E|4u; |πhence |ε1|4α=↓|4|=7q|4α_↓|4
 6455  q|4|¬W|4u/(v|4α_↓|4b|gn|gα_↓|g2)|4α_↓|4u/v|4α+↓|41|4α_↓|43/b
 6455  ; |πthat is,|'{A3}|ε|(3|d2b|)|4|¬W|4|(u|d2v|)|↔a|(b|gn|gα_↓|
 6458  g2|d2v|4α_↓|4b|gn|gα_↓|g2|)|↔s|4|¬W|4|↔a|(b|gn|gα_↓|g1|d2v|4
 6458  α_↓|4b|gn|gα_↓|g2|)|↔s.|;{A8}|πFinally, therefore, 
 6461  |εb|gn|4α+↓|43b|gn|gα_↓|g2|4|¬Q|43v; |πbut this 
 6464  contradicts the size of |εv|β1, |πunless |εb|4|¬E|43, 
 6471  |πand the exercise is obviously true when |εb|4|¬E|43.|'
 6479  |Hβ{U0}{H9L11M29}|π58320#Computer Programming!(Knuth/Addison
folio 758 galley 7
 6480  -Wesley)!f. 758!Ans!g. 7|'{A6}|≡2|≡2|≡.|9|4Let 
 6484  |εu|4α=↓|44100, v|4α=↓|4588. |πWe _rst try |ε|=7q|4α=↓|4|"l|
 6489  f41|d35|)|"L|4α=↓|48, |πbut 8|4|¬O|48|4|¬Q|410(41|4α_↓|440)|
 6491  4α+↓|40|4α=↓|410. Then we set |ε|=7q|4α=↓|47, 
 6496  |πand now we _nd 7|4|¬O|48|4|¬W|410(41|4α_↓|435)|4α+↓|40|4α=
 6500  ↓|460. But 7 times 588 equals 4116, so the true 
 6510  quotient is |εq|4α=↓|46. |π(Incidentally, this 
 6515  example shows that Theorem B cannot be improved 
 6523  under the given hypotheses, when |εb|4α=↓|410.)|'
 6529  {A3}|π|≡2|≡3|≡.|9|4Obviously |εv|"lb/(v|4α+↓|41)|"L|4|¬W|4(v
 6530  |4α+↓|41)|"lb/(v|4α+↓|41)|"L|4|¬E|4(v|4α+↓|41)b/(v|4α+↓|41)|
 6530  4α=↓|4b; |πalso if |εv|4|¬R|4|"lb/2|"L |πwe obviously 
 6536  have |εv|"lb/(v|4α+↓|41)|"L|4|¬R|4v|4|¬R|4|"lb/2|"L. 
 6538  |πFinally, assume that |ε1|4|¬E|4v|4|¬W|4|"lb/2|"L. 
 6542  |πThen |εv|"lb/(v|4α+↓|41)|"L|¬Q|4v{H11}(b/(v|4α+↓|41)|4α_↓|
 6543  41{H11}){H9}|4|¬R|4b/2|4α_↓|41|4|¬R|4|"lb/2|"L|4α_↓|41, 
 6544  |πbecause |εv{H11}({H9}b/(v|4α+↓|41)|4α_↓|41{H11}){H9}|4α_↓|
 6545  4b/2|4α+↓|41|4α=↓|4(b/2|4α_↓|4v|4α_↓|41)(v|4α_↓|41)/(v|4α+↓|
 6545  41)|4|¬R|40. |πFinally since |εv|"lb/(v|4α+↓|41)|"L|4|¬Q|4|"
 6548  lb/2|"L|4α_↓|41, |πwe must have |εv|"lb/(v|4α+↓|41)|"L|4|¬R|
 6552  4|"lb/2|"L.|'{A3}|π|≡2|≡4|≡.|9|4The probability 
 6555  is only log|ε|βb|42, not |f1|d32|)*3 |π(For example, 
 6562  if |εb|4α=↓|42|g3|g5, |πthe probability is approximately 
 6568  |f1|d335|); this is still high enough too warrant 
 6576  the special test for |εd|4α=↓|41 |πin steps D1 
 6584  and D8.)|'{A3}|≡2|≡5|≡.|'{A3}|h|∂!!|2|∂000!|∂|¬2|¬h!|∂|¬e|¬n
 6587  |¬t|¬a!|?|¬d|¬i|¬v|¬b|¬y|¬z|¬e|¬r|¬o!|∂!|εA(M|4α+↓|4N)!|∂!|π
 6588  Otherwise compute |εb/(v|β1|4α+↓|41).|∂|E|n|'
 6591  |>|;|*/|↔c|↔c|↔P|'|;|\|π|¬e|¬n|¬t|¬a|'|¬1|'1|;
 6598  >|>|;|*/|↔c|↔c|↔L|\|'|;|¬a|¬d|¬d|'|¬v|≤%|¬1|'1|;
 6606  >|>|;|*/|↔c|↔c|↔M|\|'|;|¬s|¬t|¬a|'|¬t|¬e|¬m|¬p|'
 6613  1|;>|>|;|*/|↔c|↔c|↔C|'|\|;|¬e|¬n|¬t|¬a|'|¬1|'1|;
 6622  >|>|;|*/|↔c|↔c|↔o|'|;|\|¬j|¬o|¬v|'|¬1|¬f|'1|;Jump 
 6631  if |εv|β1|4α=↓|4b|4α_↓|41.|'>|>|;|*/|↔c|↔c|↔p|\|'
 6637  |;|π|¬e|¬n|¬t|¬x|'|¬0|'1|;>|>|;|*/|↔c|↔c|↔l|\|'
 6645  |;|¬d|¬i|¬v|'|¬t|¬e|¬¬m|¬|;|¬d|¬i|¬v|'|¬t|¬e|¬m|¬p|'
 6650  1|;Otherwise compute |εb/(v|β1|4α+↓|41).|'>|>
 6656  |;|π|*/|↔c|↔c|↔m|'|\|;|¬j|¬o|¬v|'|¬d|¬i|¬v|¬b|¬y|¬z|¬e|¬r|¬o|
 6660  '1|;Jump if |εv|β1|4α=↓|40.|'>|>|;|*/|↔c|↔O|↔c|\|'
 6669  |π|¬1|¬h|'|¬s|¬t|¬a|'|¬d|'1|;>|>|;|*/|↔c|↔O|↔O|\|'
 6677  |;|¬d|¬e|¬c|¬a|'|¬1|'1|;>|>|;|*/|↔c|↔O|↔P|\|'|;
 6686  |¬j|¬a|¬n|¬z|'α/↓|≤%|¬3|'1|;Jump if |εd|4|=|↔6α=↓|41.|'
 6692  >|>|;|*/|↔c|↔O|↔L|'|;|\|¬s|¬t|¬z|'|¬u|'1|4α_↓|4A|;
 6700  >|>|;|π|*/|↔c|↔O|↔M|\|'|;|¬j|¬m|¬p|'|¬d|¬2|'|ε1|4α_↓|4A|;
 6708  >|>|;|π|*/|↔c|↔O|↔C|\|'|;|¬e|¬n|¬t|¬1|'|¬n|'|εA|;
 6716  |πMultiply |εv |πby |εd.|'>|>|;|π|*/|↔c|↔O|↔o|'
 6724  |;|\|¬e|¬n|¬t|¬x|'|¬0|'|εA|;>|>|;|π|*/|↔c|↔O|↔p|\|'
 6732  |¬2|¬h|'|¬s|¬t|¬x|'|¬c|¬a|¬r|¬r|¬y|'|εAN|;>|>
 6738  |;|π|*/|↔c|↔O|↔l|\|'|;|¬l|¬d|¬a|'|¬v|¬,|¬1|'|εAN|;
 6744  >|>|;|π|*/|↔c|↔O|↔m|\|'|;|¬m|¬u|¬l|'|¬d|'|εAN|;
 6752  >|>|;|2.|5.|5.|'|;|;|;|;|π(as in exercise 13)|'
 6764  >|>|;|*/|↔c|↔P|↔o|'|;|\|¬j|¬1|¬p|'|¬2|¬b|'|εAN|;
 6772  >|>|;|π|*/|↔c|↔P|↔p|\|'|;|¬e|¬n|¬t|¬1|'|¬m|≤%|¬n|'
 6779  |εA|;|π(Now rX|4α=↓|40.)|'>|>|;|*/|↔c|↔P|↔l|\|'
 6786  |¬2|¬h|'|¬s|¬t|¬x|'|¬c|¬a|¬r|¬r|¬y|'|εA(M|4α+↓|4N)|;
 6790  |πMultiply |εu |πby |εd.|'>|>|;|π|*/|↔c|↔P|↔m|\|'
 6798  |;|¬l|¬d|¬a|'|¬u|¬,|¬1|'|εA(M|4α+↓|4N)|;>|>|;
 6805  |2.|5.|5.|'|;|;|;|;|π(as in exercise 13)|'>|>
 6816  |;|*/|↔c|↔L|↔p|\|'|;|¬j|¬1|¬p|'|¬2|¬b|'|εA(M|4α+↓|4N)|'
 6822  >|>|;|π|*/|↔c|↔L|↔l|'|;|\|¬s|¬t|¬x|'|¬u|'|εA|;
 6830  >{A3}|π|≡2|≡6|≡.|9|4(See the algorithm of exercise 
 6836  16.)|'{A3}|h|∂!!|2000!|∂|¬d|¬h!|∂|¬e|¬n|¬n|¬i!|∂|¬u|≤%|¬m|≤%
 6837  |¬n|≤%|¬1|¬,|¬,!|∂|εAN!|∂!|π(Remainder|6will|6be|6left|6in|6
 6837  loca-|∂|E|n|'|>!!|2|*/|↔O|↔c|↔O|'|\|¬d|¬8|'|¬l|¬d|¬a|'
 6842  |¬d|'1!|;!(Remainder will be left in loca-|'>
 6851  |>!!|2|*/|↔O|↔c|↔P|'|;|\|¬d|¬e|¬c|¬a|'|¬1|'1!|;
 6857  !!tions |¬u|≤%|¬m|≤%|¬1 through |¬u|≤%|¬m|≤%|¬n)|'
 6861  >|>!!|2|*/|↔O|↔c|↔L|\|'|;|¬j|¬a|¬z|'|¬d|¬o|¬n|¬e|'
 6867  1!|;!Terminate if |εd|4α=↓|41.|'>|>!!|2|*/|↔O|↔c|↔L|\|'
 6874  |;|¬e|¬n|¬n|¬i|'|¬n|'A!|;!|πrI1|4|"o|4|εj|4α_↓|4n|4α_↓|41; 
 6879  j|4|¬L|41.|'>|π|>!!|2|*/|↔O|↔c|↔C|\|'|;|¬e|¬n|¬t|¬a|'
 6885  |¬o|'|εA!|;!r|4|¬L|40.|'>|>!!|2|π|*/|↔O|↔c|↔o|\|'
 6891  |¬1|¬h|'|¬l|¬d|¬x|'|¬u|≤%|¬m|≤%|¬n|≤%|¬1|¬,|¬1|'
 6894  |εAN!|;!|πrAX|4|¬L|4|εrb|4α↓|4u|βm|βα+↓|βj.|'
 6896  >|π|>!!|2|*/|↔O|↔c|↔p|\|'|;|¬d|¬i|¬v|'|¬d|'|εAN!|;
 6903  >|>|π!!|2|*/|↔O|↔c|↔l|\|'|;|¬s|¬t|¬a|'|¬u|≤%|¬m|≤%|¬n|≤%|¬1|¬
 6908  ,|¬1|'|εAN!|;>|π|>!!|2|*/|↔O|↔c|↔m|\|'|;|¬s|¬l|¬a|¬x|'
 6915  |¬5|'|εAN!|;!r|4|¬L|4(rb|4α↓|4u|βm|βα↓|βj)|πmod|4|εd.|π|'
 6918  >|>!!|2|*/|↔O|↔O|↔c|\|'|;|¬i|¬n|¬c|¬2|'|¬1|'|εAN!|;
 6925  !j|4|¬L|4j|4α↓|41.|'>|>|π!!|2|*/|↔O|↔O|↔O|'|\|;
 6930  |¬j|¬2|¬n|'|¬1|¬B|'|εAN!|;!|πRepeat for 1|4|¬E|4|εj|4|¬E|4n.
 6935  |'>{A9}|πAt this point, the division routine 
 6943  is complete; and by the next exercise, register 
 6951  AX is zero.|'{A3}|≡2|≡7|≡.|9|4It is |εde|4|πmod|4|εdv|4α=↓|4
 6956  d(u|4|πmod|4|εv).|'{A3}|π|≡2|≡8|≡.|9|4For convenience, 
 6959  let us assume |εv |πhas a decimal point at the 
 6969  left, that is, |εvN46α=*?*?*?*?{A3}|≡2|≡7|≡.|9|4It 
 6973  is |εde|4|πmod|4|εdv|4α=↓|4d(u|4|πmod|4|εv).|'
 6975  {A3}|π|≡2|≡8|≡.|9|4For convenience, let us assume 
 6980  |εv |πhas a decimal point at the left, that is, 
 6990  |εv|4α=↓|4(v|β0|β.v|β1|β2|4.|4.|4.). |πAfter 
 6992  step N1 we have |f1|d32|)|4|¬E|4|εv|4|¬W|41|4α↓|41/b: 
 6997  |πfor|'{A9}|εv|↔d|(b|4α+↓|41|d2v|β1|4αt↓|41|)|↔f|4|∂|¬E|4|(v
 6998  (b|4α+↓|41)|d2v|β1|4α+↓|41|)|4α=↓|4|(v(1|4α+↓|41/b)|d2(1/b)(
 6998  v|β1|4α↓|41)|)|4|¬W|41|4α+↓|4|(1|d2b|)|1|1,|;
 6999  |πand|'|ε| v|↔d|(b|4α+↓|41|d2v|β1|4α+↓|41|)|↔f|4|L|¬R|4|(v(b
 7000  |4αt↓|41|4α_↓|4v|β1)|d2v|β1|4α+↓|41|)|4|¬R|4|(1|d2b|)|4|(v|β
 7000  1(b|4α+↓|41|4α_↓|4v|β1)|d2v|β1|4α+↓|41|)|1|1.>
 7001  {A9}|πThe latter quantity takes its smallest 
 7007  value when |εv|β1|4α=↓|41, |πsince it is a convex 
 7015  function and the other extreme value is greater.|'
 7023  !!|2The formula in step N2 may be written|'{A9}|εv|4|¬L|4|↔d
 7031  |(b(b|4α+↓|41)|d2v|β1|4α+↓|41|)|↔f|1|1|(v|d2b|)|1|1,|;
 7032  {A9}|πso we see as above that |εv |πwill never 
 7041  become |→|¬R1|4α+↓|41/|εb.|π|'!!|2The minimum 
 7045  value of |εv |πafter one iteration of step N2 
 7054  is |→|¬R|'{A9}|9|4|↔a|(|εb(b|4α+↓|41)|4α_↓|4v|β1|d2v|β1|4α+↓
 7056  |41|)|↔s|1|1|(v|d2b|)|4|¬R|4|↔a|(b(b|4α+↓|41)|4α_↓|4v|β1|d2v
 7056  |β1|4α↓|41|)|↔s|1|1|(v|β1|d2b|β2|)|4|∂α=↓|4|↔a|(b(b|4α+↓|41)
 7056  |4α+↓|41|4α_↓|4t|d2t|)|↔s|↔a|(t|4α_↓|41|d2b|g2|)|↔s|'
 7057  {A4}|Lα=↓|41|4α+↓|4|(1|d2b|)|4α↓|4|(2|d2b|g2|)|4α_↓|4|(1|d2b
 7057  |g2|)|1|1|↔at|4α+↓|4|(b(b|4α+↓|41)|4α+↓|41|d2t|)|↔s,>
 7058  {A9}|πif |εt|4α=↓|4v|β1|4α+↓|41. |πThe minimum 
 7062  of this quantity occurs for |εt|4α=↓|4b/2|4α+↓|41; 
 7068  |πa lower bound is |ε1|4α_↓|43/2b. |πHence |εv|β1|4|¬R|4b|4α
 7074  _↓|42, |πafter one iteration of step N2. Finally, 
 7082  we have |ε(1|4α_↓|43/2b)(1|4αt↓|41/b)|g2|4|¬Q|41, 
 7085  |πwhen |εb|4|¬R|45, |πso at most two more iterations 
 7093  are needed. The assertion is easily veri_ed when 
 7101  |εb|4|¬W|45.|'{A3}|π|≡2|≡9|≡.|9|4True, since 
 7104  |ε(u|βj|4.|4.|4.|4u|βj|βα+↓|βn)|βb|4|¬W|4v. |π(But 
 7106  in Program D, |εu|βj |πis left as |εb|4α_↓|41 
 7114  |πif step D6 is necessary, since there was no 
 7123  need to reset |εu|βj |πwhen it was never being 
 7132  used in the subject calculation.)|'{A3}|≡3|≡0|≡.|9|4In 
 7138  Algorithms A and S, such overlap is possible 
 7146  if the algorithms are rewritten slightly; e.g., 
 7153  in Algorithm A, we could rewrite step A2 thus: 
 7162  ``Set |εt|4|¬L|4u|βj|4α+↓|4v|βj|4α+↓|4k, w|βj|4|¬L|4t|4|πmod
 7164  |4|εb, k|4|¬L|4|"lt/b|"L.''|'|π!!|2In Algorithm 
 7168  M, |εv|βj |πmay be in the same location as |εw|βj. 
 7178  |πIn Algorithm D, it is most convenient (as in 
 7187  Program D, exercise 26) to let |εr|β1|4.|4.|4.|4r|βn 
 7194  |πbe the same as |εu|βm|βα+↓|β1|4.|4.|4.|4u|βm|βα+↓|βn; 
 7199  |πand we can also have |εq|β0|4.|4.|4.|4q|βm 
 7205  |πthe same as |εu|β0|4.|4.|4.|4u|βm, |πprovided 
 7210  that no alteration of |εu|βj |πis made in step 
 7219  D6. (Such an alteration is unnecessary, as mentioned 
 7227  in exercise 29.)|'{A3}|≡3|≡1|≡.|9|4One possibility 
 7232  is this, if we consider the situation of Fig. 
 7241  6 with |εu|4α=↓|4u|βju|βj|βα+↓|β1|4.|4.|4.|4u|βj|βα+↓|βn 
 7244  |πas in Algorithm D: If the leading nonzero digits 
 7253  of |εu |πand |εv |πhave the same sign, set |εr|4|¬L|4u|4α_↓|
 7262  4v, q|4|¬L|41; |πotherwise set |εr|4|¬L|4u|4α+↓|4v, 
 7267  q|4|¬L|4|→α_↓1. |πNow if |ε|¬Gr|¬G|4|¬Q|4|¬Gu|¬G, 
 7271  |πor if |ε|¬Gr|¬G|4α=↓|4|¬Gu|¬G |πand the _rst 
 7277  nonzero digit of |εu|βj|βα+↓|βn|βα+↓|β1|4.|4.|4.|4u|βm|βα+↓|
 7280  βn |πhas the same sign as the _rst nonzero digit 
 7290  of |εr, |πset |εq|4|¬L|40; |πotherwise set |εu|βj|4.|4.|4.|4
 7296  u|βj|βα+↓|βn|4|¬L|4r.|'{A3}|π|≡3|≡6|≡.|9|4Values 
 7298  to 1000 decimal and 1100 octal places have been 
 7307  computed by R. P. Brent, Tech. Rep. 47, Comp. 
 7316  Centre, Australian Nat. Univ., Canberra, 1975.|'
 7322  {A25}{H10L12}|*/|\|∨S|∨E|∨C|∨T|∨I|∨O|∨N|9|∨4|∨.|∨3|∨.|∨2|'
 7323  {A11}{H9L11}|9|1|≡1|≡.|9|4The solution is unique 
 7327  since 7|4|¬O|411|4|¬O|413|4α=↓|41001. The ``constructiave'' 
 7331  proof of Theorem C tells us that the answer is 
 7341  {H11}({H9}(11|4|¬O|413)|g6|4α+↓|4(7|4|¬O|413)|g1|g0|4α+↓|45|
 7341  4|¬O|4(7|4|¬O|411)|g1|g2{H11}){H9}mod|41001. 
 7342  This answer is perhaps not explicit enough*3 By 
 7350  (23) we have |εv|β1|4α=↓|41, v|β2|4α=↓|4(6|4α_↓|41)|4|¬O|48|
 7354  4|πmod|411|4α=↓|47, v|β3|4α=↓|4{H11}({H9}(5|4α_↓|41)|4|¬O|42
 7355  |4α_↓|47{H11}){H9}|4|¬O|46|4mod|413|4α=↓|46, 
 7356  so |εu|4α=↓|46|4|¬O|47|4|¬O|411|4α+↓|47|4|¬O|47|4α+↓|41|4α=↓
 7357  |4512.|'{A3}|π|9|1|≡2|≡.|9|4Yes (by the ``constructive'' 
 7362  proof given, but not by the ``nonconstructive'' 
 7369  proof).|'{A3}|9|1|≡3|≡.|9|4|εu|4|"o|4u|βi (|πmodulo 
 7372  |εm|βi) |πimplies that |εu|4|"o|4u|βi |π{H11}({H9}modulo|4gc
 7376  d(|εm|βi,|4m|βj){H11}){H9}, |πso the condition 
 7380  |εu|βi|4|"o|4u|βj {H11}({H9}|πmodulo gcd(|εm|βi,|4m|βj){H11}
 7382  ){H9} |πmust surely hold if there is a solution. 
 7391  Furthermore if |εu|4|"o|4v |π(modulo |εm|βj) 
 7396  |πfor all |εj, |πthen |εu|4α_↓|4v |πis a multiple 
 7404  of lcm(|εm|β1,|4.|4.|4.|4,|4m|βr)|4α=↓|4m; |πhence 
 7407  there is at most one solution.|'!!|2The proof 
 7415  can now be completed in a nonconstructive manner 
 7423  by counting the number of di=erent sets |ε(u|β1,|4.|4.|4.|4,
 7430  |4u|βr) |πsatisfying the conditions 0|4|¬E|4u|βj|4|¬W|4m|βj 
 7435  |πand |εu|βi|4|"o|4u|βj {H11}({H9}|πmodulo gcd|ε(m|βi,|4m|βj
 7438  ){H11}){H9}. If this number is |εm, |πthere must 
 7446  be a solution since |ε(u|4|πmod.|εm|β1,|4.|4.|4.|4,|4u|4|πmo
 7450  d|4|εm|βr) |πtakes on |εm |πdistinct values as 
 7457  |εu |πgoes from |εa |πto |εa|4α+↓|4m. |πAssume 
 7464  that |εu|β1,|4.|4.|4.|4,|4u|βr|βα_↓|β1 |πhave 
 7467  been chosen satisfying the given conditions; 
 7473  we must now pick |εu|βr|4|"o|4u|βj |π{H11}({H9}modulo 
 7479  gcd|ε(m|βj,|4m|βr){H11}){H9} for 1|4|¬E|4j|4|¬W|4r, 
 7482  |πand by the generalized Chinese Remainder Theorem 
 7489  for |εr|4α_↓|41 |πelements there are|'{A9}|εm|βr/|πlcm{H11}(
 7494  {H9}gcd|ε(m|β1,|4m|βr),|4.|4.|4.|4,|4|πgcd|ε(m|βr|βα_↓|β1,|4
 7494  m|βr){H11}){H9}|4|∂α=↓|4m|βr/|πgcd{H11}({H9}lcm|ε(m|β1,|4.|4
 7494  .|4.|4,|4m|βr|βα_↓|β1),|4m|βr{H11}){H9}|'{A4}|Lα=↓|4|πlcm(|ε
 7495  m|β1,|4.|4.|4.|4,|4m|βr)/|πlcm(|εm|β1,|4.|4.|4.|4,|4m|βr|βα_
 7495  ↓|β1)>{A9}|πways to do this. [This proof is based 
 7504  on identities (10), (11), (12), and (14) of Section 
 7513  4.5.2.]|'!!|2A constructive proof [A. S. Fraenkel, 
 7520  |εProc. AMS |≡1|≡5 (1963), 790<791] |πgeneralizing 
 7526  (24) can be given as follows. Let |εM|βj|4α=↓|4|πlcm|ε(m|β1,
 7533  |4.|4.|4.|4,|4m|βj); |πwe wish to _nd |εu|4α=↓|4v|βrM|βr|βα_
 7538  ↓|β1|4α+↓|4|¬O|4|¬O|4|¬O|4α+↓|4v|β2M|β1|4α+↓|4v|β1, 
 7539  |πwhere 0|4|¬E|4|εv|βj|4|¬W|4M|βj/M|βj|βα_↓|β1. 
 7541  |πAssume that |εv|β1,|4.|4.|4.|4,|4v|βj|βα_↓|β1 
 7544  |πhave already been determined; then we must 
 7551  solve the congruence|'{A9}|εv|βjM|βj|βα_↓|β1|4α+↓|4v|βj|βα_↓
 7554  |β1M|βj|βα_↓|β2|4α+↓|4|¬O|4|¬O|4|¬O|4α+↓|4v|β1|4|"o|4u|βj!|π
 7554  (modulo|4|εm).|;{A9}|πGere |εv|βj|βα_↓|β1M|βj|βα_↓|β2|4α+↓|4
 7556  |¬O|4|¬O|4|¬O|4α+↓|4v|β1|4|"o|4u|βi|4|"o|4u|βj 
 7557  |π{H11}({H9}modulo gcd|ε(m|βi,|4m|βj){H11}){H9} 
 7559  |πfor |εi|4|¬W|4j |πby hypothesis, so |εc|4α=↓|4u|βj|4α_↓|4(
 7564  v|βj|βα_↓|β1M|βj|βα_↓|β2|4α+↓|4|¬O|4|¬O|4|¬O|4α+↓|4v|β1) 
 7565  |πis a multiple of|'|Hβ*?*?*?{U0}{H9L11M29}|π58320#Computer 
folio 761 galley 8
 7570  Programming!(Knuth/Addison-Wesley)!f. 761!Ans!g. 
 7572  8|'{A9}lcm{H11}({H9}gcd(|εm|β1,|4m|βj),|4.|4.|4.|4,|4|πgcd|ε
 7573  (m|βj|βα_↓|β1,|4m|βj){H11}){H9}|4α=↓|4|πgcd(|εM|βj|βα_↓|β1,|
 7573  4m|βj)|4α=↓|4d|βj.|;{A9}|πWe therefore must solve 
 7578  |εv|βjM|βj|βα_↓|β1|4|"o|4c |π(modulo |εm|βj). 
 7581  |πBy Euclid's algorithm there is a number |εc|βj 
 7589  |πsuch that |εc|βjM|βj|βα_↓|β1|4|"o|4f|βj(|πmodulo 
 7592  |εm|βj); |πhence we may take|'{A9}|εv|βj|4α=↓|4(c|βjc)/d|βj|
 7597  4|πmod|ε(m|βj/d|βj).|;{A9}|πNote that, as in 
 7602  the nonconstructive proof, we have |εm|βj/d|βj|4α=↓|4M|βj/M|
 7607  βj|βα_↓|β1.|'{A3}|π|9|1|≡4|≡.|9|4(After |εm|β4|4α=↓|491|4α=↓
 7609  |47|4|¬O|413, |πwe have used up all products 
 7616  of two or more odd primes that can be less than 
 7627  100, so |εm|β5,|4.|4.|4. |πmust all be prime.)|'
 7634  {A9}|εm|β7|h|β7|n|4|∂α=↓|479,!m|β8|h|β8|n|4|∂α=↓|473,!m|β9|h
 7634  |β9|n|4|∂α=↓|471,!m|β1|β0|4|∂α=↓|467,!m|β1|β1|4|∂α=↓|461,|;
 7635  {A4}| m|β1|β2|4|Lα=↓|459,| m|β1|β3|4|Lα=↓|453,| m|β1|β4|4|Lα
 7635  =↓|447,| m|β1|β5|4|Lα=↓|443,| m|β1|β6|4|Lα=↓|441,>
 7636  {A4}| m|β1|β7|4|Lα=↓|437,| m|β1|β8|4|Lα=↓|431,| m|β1|β9|4|Lα
 7636  =↓|429,| m|β2|β0|4|Lα=↓|423,| m|β2|β1|4|Lα=↓|417,>
 7637  {A9}|πand then we are stuck |ε(m|β2|β2|4α=↓|41 
 7643  |πdoes no good).|'{A3}|9|1|≡5|≡.|9|4No; an obvious 
 7649  upper bound is|'{A3}3|g45|g27|g211|g1|4|¬O|4|¬O|4|¬O|4α=↓|4|
 7652  ≥u|uc|)|εp|1|1|πodd|d|εp|1|1|πprime|)|4|εp|g|"l|π|gl|go|gg|ε
 7652  |rp|1|1|g1|g0|g0|g|"L.|;{A9}|πThis upper bound 
 7656  is attained if we choose |εm|β1|4α=↓|43|g4, m|β2|4α=↓|45|g2,
 7662   |πetc. (It is  more di∃cult, however, to maximize 
 7672  |εm|β1|4.|4.|4.|4m|βr |πwhen |εr |πis _xed, or 
 7678  to maximize |εm|β1|4α+↓|4|¬O|4|¬O|4|¬O|4α+↓|4m|βr 
 7681  |πas we would attempt to do using moduli |ε2|gm|rj|4α_↓|41.)
 7689  |'{A3}|π|9|1|≡6|≡.|9|4a) If |εe|4α=↓|4f|4α+↓|4kg, 
 7693  |πthen |ε2|ge|4α=↓|42|gf(2|gg)|gk|4|"o|42|gf|4|¬O|41|gk 
 7695  |π(modulo 2|ε|gg|4α_↓|41). |πSo if |ε2|ge|4|"o|42|gf 
 7700  |π(modulo 2|ε|gg|4α_↓|41), |πthen 2|ε|ge|1|1|π|gm|go|gd|1|1|
 7703  ε|gg|4|"o|42|gf|1|1|π|gm|go|gd|1|1|ε|gg |π(modulo 
 7705  2|ε|gg|4α_↓|41), |πand since the latter quantities 
 7711  lie between zero and |ε2|gg|4α_↓|41 |πwe must 
 7718  have |εe |πmod|4|εg|4α_↓|4f |πmod|4|εg.|'!!|2|πb)|9By 
 7723  part (a),|'{A9}(1|4α+↓|42|ε|gd|4α+↓|4|¬O|4|¬O|4|¬O|4α+↓|42|g
 7725  (|gc|gα_↓|g1|g)|gd)|4|¬O|4(2|ge|4α_↓|41)|4|"o|4(1|4α+↓|42|gd
 7725  |4α+↓|4|¬O|4|¬O|4|¬O|4α+↓|42|g(|gc|gα_↓|g1|g)|gd)|4|¬O|4(2|g
 7725  d|4α_↓|41)|'{A3}α=↓|42|gc|gd|4α_↓|41|4|"o|42|gc|gc|4α_↓|41|4
 7726  |¬o|42|g1|4α_↓|41|4α=↓|41!|π(modulo 2|ε|gf|4α_↓|41).|?
 7728  {A3}|π|9|1|≡7|≡.|9|4{H11}({H9}|εu|βj|4α_↓|4(v|β1|4α+↓|4m|β1(
 7728  v|β2|4α+↓|4m|β2(v|β3|4α+↓|4|¬O|4|¬O|4|¬O|4α+↓|4m|βj|βα_↓|β2v
 7728  |βj|βα_↓|β1)|4|¬O|4|¬O|4|¬O)){H11}){H9}c|β1|βj|4.|4.|4.|4c|β
 7728  (|βj|βα_↓|β1|β)|βj|'!!!!|∂α=↓|4(u|βj|4α_↓|4v|β1)c|β1|βj|4.|4
 7729  .|4.|4c|β(|βj|βα_↓|β1|β)|βj|4α_↓|4m|β1v|β2c|β1|4.|4.|4.|4c|β
 7729  (|βj|βα_↓|β1|β)|βj|4α_↓|4|¬O|4|¬O|4|¬O|4|'{A3}α_↓|4m|β1|4.|4
 7730  .|4.|4m|βj|βα_↓|β2v|βj|βα_↓|β1c|β1|βj|4.|4.|4.|4c|β(|βj|βα_↓
 7730  |β1|β)|βj|?{A3}|L|"o|4(u|βj|4α_↓|4v|β1)c|β1|βj|4.|4.|4.|4c|β
 7731  (|βj|βα_↓|β1|β)|βj|4α_↓|4v|β2c|β2|βj|4.|4.|4.|4c|β(|βj|βα_↓|
 7731  β1|β)|βj|4α_↓|4|¬O|4|¬O|4|¬O|4α_↓|4v|βj|βα_↓|β1c|β(|βj|βα_↓|
 7731  β1|β)|βj>{A3}|Lα=↓|4{H11}({H9}|¬O|4|¬O|4|¬O|4((u|βj|4α_↓|4v|
 7732  β1)c|β1|βj|4α_↓|4v|β2)c|β2|βj|4α_↓|4|¬O|4|¬O|4|¬O|4α_↓|4v|βj
 7732  |βα_↓|β1{H11}){H9}c|β(|βj|βα_↓|β1|β)|βj!|π(modulo 
 7733  |εm|βj).>{A9}|π!!|2This method of rewriting the 
 7739  formulas uses the same number of arithmetic operations 
 7747  and fewer constants; but the number of constants 
 7755  is fewer only if we order the moduli so that 
 7765  |εm|β1|4|¬W|4m|β2|4|¬W|4|¬O|4|¬O|4|¬O|4|¬W|4m|βr, 
 7766  |πotherwise we would need a table of |εm|βi |πmod 
 7775  |εm|βj. |πThis ordering of the moduli might seem 
 7783  to require more computation than if we made |εm|β1 
 7792  |πthe largest, |εm|β2 |πthe next largest, etc., 
 7799  since there are many more operations to be done 
 7808  modulo |εm|βr |πthan modulo |εm|β1; |πbut sine 
 7815  |εv|βj |πcan be as large as |εm|βj|4α_↓|41, |πwe 
 7823  are better o= with |εm|β1|4|¬W|4m|β2|4|¬W|4|¬O|4|¬O|4|¬O|4|¬
 7827  W|4m|βr |πin (23) also. So this idea appears 
 7835  to be preferable to the formulas in the text, 
 7844  although the formulas in the text are advantageous 
 7852  when the moduli have the form (14), as shown 
 7861  in Section 4.3.3.|'{A3}|9|1|≡8|≡.|9|4|εm|βj|βα_↓|β1|4.|4.|4.
 7864  |4m|β1v|βj|4|"o|4m|βj|βα_↓|β1|4.|4.|4.|4m|β1{H11}({H9}|¬O|4|
 7864  ¬O|4|¬O|4((u|βj|4α_↓|4v|β1)c|β1|βj|4α_↓|4v|β2)c|β2|βj|4α_↓|4
 7864  |¬O|4|¬O|4|¬O|4α_↓|4v|βj|βα_↓|β1{H11}){H9}c|β(|βj|βα_↓|β1|β)
 7864  |βj|4|"o|4m|βj|βα_↓|β2|4.|4.|4.|4m|β1{H11}({H9}|¬O|4|¬O|4|¬O
 7864  |4(u|βj|4α_↓|4v|β1)c|β1|βj|4α_↓|4|¬O|4|¬O|4|¬O|4α_↓|4v|βj|βα
 7864  _↓|β2{H11}){H9}c|β(|βj|βα_↓|β2|β)|βj|4α_↓|4v|βj|βα_↓|β1m|βj|
 7864  βα_↓|β2|4.|4.|4.|4m|β1|4|"o|4|¬O|4|¬O|4|¬O|4|"o|4u|βj|4α_↓|4
 7864  v|β1|4α_↓|4v|β2m|β1|4α_↓|4|¬O|4|¬O|4|¬O|4α_↓|4v|βj|βα_↓|β1m|
 7864  βj|βα_↓|β2|4.|4.|4.|4m|β1!(|πmodulo |εm|βj).|'
 7866  {A3}|9|1|≡9|≡.|9|4u|βr|4|¬L|4{H11}({H9}(.|4.|4.|4(v|βrm|βr|β
 7866  α_↓|β1|4α+↓|4v|βr|βα_↓|β1)m|βr|βα_↓|β2|4α+↓|4|¬O|4|¬O|4|¬O)m
 7866  |β1|4α+↓|4v|β1{H11}){H9}|4|πmod|4|εm|βr,|4.|4.|4.|4,|'
 7867  u|β2|4|¬L|4(v|β2m|β1|4α+↓|4v|β1|πmod|4|εm|β2,|4u|β1|4|¬L|4v|
 7867  β1|4|πmod|4|εm|β1.|?{A9}|π(The computation should 
 7871  be done in this order, if we want to let |εu|βj 
 7882  |πand |εv|βj |πshare the same memory locations 
 7889  as is possible in (23).{H11}){H9}|'{A3}|≡1|≡0|≡.|9|4If 
 7895  we rede_ne the ``mod'' operator so that it produces 
 7904  residues in the symmetrical range, the basic 
 7911  formulas (2), (3), (4) for arithmetic and (23), 
 7919  (24) for conversiond remain the same, and the 
 7927  number |εu |πin (24) lies in the desired range 
 7936  (10). {H11}({H9}Here (24) is a |εbalanced mixed 
 7943  radix |πnotation, generalizing ``balanced-ternary'' 
 7947  notation.{H11}){H9} The comparison of two numbers 
 7953  may still be done from left to right, in the 
 7963  simple manner described in the text. Furthermore, 
 7970  it is possible to retain the value |εu|βj |πin 
 7979  a single computer word, if we have signed magnitude 
 7988  representation within the computer, even if |εm|βj 
 7995  |πis almost twice the word size. But the arithmetic 
 8004  operations analogous to (11) and (12) are more 
 8012  di∃cult, so it appears that on most computers 
 8020  this idea would result in slightly slower operation.|'
 8028  {A3}|≡1|≡1|≡.|9|4Multiply by|'|ε|(m|4α+↓|41|d22|)|4α=↓|4|↔a|
 8030  (m|β1|4α+↓|41|d22|)|1|1,|4.|4.|4.|4,|4|(m|βr|4α+↓|41|d22|)|↔
 8030  s.|;|πNote that|'|ε2t|4|¬O|4|(m|4α+↓|41|d22|)|4|"o|4t!|π(mod
 8033  ulo|4|εm).|;{A9}|πIn general if |εv |πis relatively 
 8040  prime to |εm, |πthen we can _nd (by Euclid's 
 8049  algorithm) a number |εv|¬S|4α=↓|4(v|ur|↔0|)1|),|4.|4.|4.|4,|
 8052  4v|ur|↔0|)r|)) |πsuch that |εvv|¬S|4|"o|41 |π(modulo|4|εm); 
 8057  |πand then if |εu |πis known to be a multiple 
 8067  of |εv |πwe have |εu/v|4α=↓|4uv|¬S, |πwhere the 
 8074  latter is computed with modular multiplication. 
 8080  When |εv |πis not relatively prime to |εm, |πdivision 
 8089  is much more di∃cult.|'{A3}|π|≡1|≡2|≡.|9|4Obvious 
 8094  from (11), if we replace |εm|βj |πby |εm.|'{A3}|π|≡1|≡3|≡.|9
 8102  |4(a) |εx|g2|4α_↓|4x|4α=↓|4(x|4α_↓|41)x|4|"o|40 
 8104  |π(modulo 10|ε|gn) |πis equivalent to |ε(x|4α_↓|41)x|4|"o|40
 8109   |π(modulo |εp|gn) |πfor |εp|4α=↓|42 |πand 5. 
 8116  Either |εx |πor |εx|4α_↓|41 |πmust be a multiple 
 8124  of |εp, |πand then the other is relatively prime 
 8133  to |εp|gn; |πso either |εx |πor |εx|4α_↓|41 |πmust 
 8141  be a multiple of |εp|gn. |πIf |εx|4|πmod|4|ε2|gn|4α=↓|4x|4|π
 8147  mod|4|ε5|gn|4α=↓|40 |πor 1, we must have |εx|4α=↓|40 
 8154  |πor 1; hence |εx|4|πmod|4|ε2|gn|4|=|↔6α=↓|4x 
 8158  |πmod|4|ε5|gn. |π(b) If |εx|4α=↓|4qp|gn|4α+↓|4r, 
 8162  |πwhere |εr|4α=↓|40 |πor 1, then |εr|4|"o|4r|g2|4|"o|4r|g3, 
 8168  |πso |ε3x|g2|4α_↓|42x|g3|4|"o|4(6qp|gnr|4α+↓|43r)|4α_↓|4(6qp
 8169  |gnr|4α+↓|42r)|4|"o|4r|π(modulo|4|εp|gn). |π(c) 
 8171  Let |εc|¬S|4α=↓|4{H11}({H9}3(cx)|g2|4α_↓|42(cx)|g3{H11}){H9}
 8172  /x|g2|4α=↓|43c|g2|4α_↓|42c|g3x.|'!!|2|π|εNote|*/:|\ 
 8174  |πSince the last |εk |πdigits of an |εn-|πdigit 
 8182  automorph form a |εk-|πdigit automorph, it makes 
 8189  sense to speak of the two |¬X-digit automorphs, 
 8197  |εx |πand 1|4α_↓|4|εx, |πwhich are 10-adic numbers 
 8204  (cf. exercise 4.1<31). Th*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!
 8207